#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl; typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl; typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl; typedef vector vs; typedef vector vb; typedef queue qi; typedef queue ql; typedef queue qpi; typedef queue qpl; typedef queue qti; typedef queue qtl; #define fastio(x, y) cin.tie((x))->sync_with_stdio((y)) #define X first #define Y second #define pb push_back #define sz(x) (int((x).size())) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() const char nl = '\n'; int n; vector adj[100'005]; int a[100'005]; int depth[100'005], chk[100'005], start_idx[100'005]; bool is_correct_path(int cur) { if(sz(adj[cur]) == 1) { return 1; } bool ans = 1; int& st = start_idx[depth[cur] + 1]; int en = upper_bound(chk, chk + n, depth[cur] + 1) - chk; while(st < en) { if(!binary_search(all(adj[cur]), a[st])) { return 0; } ans &= is_correct_path(a[st]); st++; } return ans; } int main() { fastio(nullptr, false); cin >> n; for(int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) { sort(all(adj[i])); } queue q; depth[a[0]] = 1; q.push(a[0]); while(sz(q)) { auto cur = q.front(); q.pop(); for(auto nxt : adj[cur]) { if(depth[nxt] == 0 || depth[nxt] > depth[cur] + 1) { depth[nxt] = depth[cur] + 1; q.push(nxt); } } } int mx{}; for(int i = 0; i < n; i++) { chk[i] = depth[a[i]]; mx = max(mx, chk[i]); } bool ans{}; if(is_sorted(chk, chk + n)) { start_idx[mx + 1] = 0x3f3f3f3f; for(int i = 1; i <= mx; i++) { start_idx[i] = lower_bound(chk, chk + n, i) - chk; } ans = is_correct_path(a[0]); } cout << ans; }

제출 #9869

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: