下一站 Beyond This Station

InfiniteRobin · 2026-07-19 20:11:00 · 题解

思路

考虑记录每个节点的子树中数的范围。

由于非包含关系的子树之间互不干扰，因此要满足每一个点的子节点在经过循环移位后可以拼成一个连续的区间。也就是说，我们要维护每一个结点子树的范围，这个范围由儿子转移即可，若任意一结点无法满足，答案即为 NO。

可以对子节点区间排序做到 \mathcal{O}(n \log n)，当然，由于是循环移位，也可以轻松做到 \mathcal{O}(n)。

代码

给一个 \mathcal{O}(n) 实现。

:::success[Code] 有点细节，场上吃了两发罚时。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n, cnt;
bool ok = 1;
int l[N], r[N], le[N];
vector <int> g[N];

void dfs(int k){
    if(l[k] != 0 || ok == 0) return;
    int minn = 1e9, maxn = 0; 
    for(int i : g[k]){
        dfs(i);
        minn = min(minn, l[i]);
        maxn = max(maxn, r[i]);
        le[k] += le[i];
    }
    int fir = 0, la = 0, f = 1;
    for(int i : g[k]){
        if(fir == 0) fir = l[i];
        else{
            if(l[i] < (la + 1)){
                if(f == 0){
                    ok = 0;
                    return;
                }
                f = 0;
            }
            else if(l[i] > la + 1){
                ok = 0;
                return;
            }
        }
        la = r[i];
    }
    l[k] = minn, r[k] = maxn;
    if(r[k] - l[k] + 1 != le[k]) ok = 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int T;
    cin >>T;
    while(T --){
        cin >>n;
        ok = 1;
        for(int i = 1; i <= n; i ++) g[i].clear();
        for(int i = 2, k; i <= n; i ++){
            cin >>k;
            g[k].push_back(i);
        }
        cnt = 0;
        for(int i = 1; i <= n; i ++){
            cin >>l[i];
            r[i] = l[i];
            cnt = max(cnt, l[i]);
            if(l[i]) le[i] = 1;
            else le[i] = 0;
        }
        dfs(1);

        if(ok) cout <<"YES\n";
        else cout <<"NO\n";
    }

    return 0;
}

:::