#include #include #include #include #include using namespace std; vector> child; vector min_v, max_v; bool DFS(int root, int &minv, int &maxv) { bool good = true; minv = min_v[root]; maxv = max_v[root]; int prev_max = INT_MIN; for (auto c : child[root]) { int mincv, maxcv; good &= DFS(c, mincv, maxcv); good &= prev_max < mincv; prev_max = max(prev_max, maxcv); minv = min(minv, mincv); maxv = max(maxv, maxcv); } return good; } bool allgood(int n, int m, const vector &visit) { min_v.clear(); min_v.resize(n, INT_MAX); max_v.clear(); max_v.resize(n, INT_MIN); for (int i = 0; i < m; i++) { int d = visit[i]; min_v[d] = min(min_v[d], i); max_v[d] = max(max_v[d], i); } int minv, maxv; return DFS(0, minv, maxv); } void solve() { int n, m; cin >> n >> m; child.clear(); child.resize(n); for (int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; child[a-1].insert(b-1); } vector visit(m); for (auto &x : visit) { cin >> x; x--; } int lo = 1; // lo possible int hi = m+1; // hi impossible while (hi - lo > 1) { int mid = lo + (hi-lo)/2; if (allgood(n, mid, visit)) { lo = mid; } else { hi = mid; } } cout << lo << endl; } int main() { solve(); return 0; }