「2025CCPC济南」J. 记忆，排列和有根树题解

## [题目链接](https://qoj.ac/contest/2607/problem/15041)

这题重要的是**逆向思维**

首先可以把题目中的限制分成两种

对于点 $x$

#### 第一类限制

- 若 $d_x\ne-1$，则 $x$ 子树中深度小于 $dep_x+d_x$ 的点必须排在 $x$ 后面
- 若 $d_x=-1$，则 $x$ 子树中所有点必须排在 $x$ 后面

如果只考虑第一类限制，我们对先后关系建边，就相当于求字典序最小的拓扑序

但是直接连边数量会很多很多

可以反过来考虑一个点 $y$ 一定要出现在它的哪些祖先前面，按距离 $y$ 的距离记为 $x_1,x_2,x_3\cdots$

很容易发现如果 $y$ 一定要 $x_2$ 前面，即存在边 $y\rightarrow x_2$，一定存在边 $x_1\rightarrow x_2$，所以边 $y\rightarrow x_2$ 对拓扑序没有任何影响，对于 $x_3,x_4\cdots$ 同理，所以真正有用的边只有 $y\rightarrow x_1$！

我们只需要对于每个点 $y$，找到深度最大（离 $y$ 最近）的 $y$ 的祖先 $x_1$，连一条边表示 $y$ 在排列中一定要在 $x_1$ 之前！

这部分题解中给的做法是倍增，大概是记录 表示从 **$y$** 开始往上跳 **$2^k$** 步的路径上，所有节点的 **$dep_x+d_x$** 的最大值，然后跳尽量少的步数！

但可能边界情况和细节需要考虑一些，也可以像我的代码一样用线段树实现，在每一个 $dep_x+d_x-1$ 位置上记录 $dep_x$，对于每个点 $y$，在线段树上区间 $[dep_y,n]$ 内的点都要出现在 $y$ 后面，找到 $dep_x$ 最大的点连边即可！

#### 第二类限制

若 $d_x\ne-1$，则 $x$ 子树中深度为 $dep_x+d_x$ 的点至少有一个出现在 $x$ 前面

可以想象 $x$ 被锁住了，只有当它子树满足 $dep_y=dep_x+d_x$ 的点出现过才可以把他解锁！

这也要倒着考虑，对于节点 $y$，假设它能解锁的祖先按距离 $y$ 的距离记为 $x_1,x_2,x_3\cdots$

容易发现如果 $x_1$ 被解锁了（不管是不是被 $y$ 解锁的），那么 $x_2,x_3,x_4\cdots$ 一定会被同时解锁

也就是所对于每个点 $y$，它可以解锁点的会构成一个链，每次一个点被解锁后从链中删去即可！

（当然这也可以用并查集的 $fa$ 数组实现）

加上第二类先之后只需要在拓扑排序中入队时判断该点是否被解锁了！

要求字典序最小可以使用优先队列进行拓扑排序！

## CODE

```cpp
#include <bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
// #define int long long

using namespace std;

const int N=5e5+10;
int n, d[N], dep, mp[N], du[N], nxt[N], head[N], stk[N];
bool locked[N];
vector<int> e[N], E[N];
vector<int> ans;

struct seg {
    int s[N*4];

void change(int p, int l, int r, int x, int v) {
        if (l==r) {
            s[p]=v;
            return;
        }
        int mid=l+r>>1;
        if (x<=mid) change(lp, l, mid, x, v);
        else change(rp, mid+1, r, x, v);
        s[p]=max(s[lp], s[rp]);
    }

int ask(int p, int l, int r, int L, int R) {
        if (L>R) return 0;
        if (L<=l && r<=R) return s[p];
        int mid=l+r>>1, res=0;
        if (L<=mid) res=ask(lp, l, mid, L, R);
        if (R>mid) res=max(res, ask(rp, mid+1, r, L, R));
        return res;
    }
} S;

void dfs(int x, int fa, int dep) {
    mp[dep]=x;
    head[x]=stk[dep];

int t=S.ask(1, 1, n, dep, n);
    if (t) E[mp[t]].push_back(x), du[x]++;

int pos=min(dep+d[x]-1, n);
    int old=S.ask(1, 1, n, pos, pos);
    S.change(1, 1, n, pos, dep);

if (dep+d[x]<=n) {
        nxt[x]=stk[dep+d[x]];
        stk[dep+d[x]]=x;
    }

for (int y:e[x])
        if (y!=fa) dfs(y, x, dep+1);

S.change(1, 1, n, pos, old);
    if (dep+d[x]<=n) stk[dep+d[x]]=nxt[x];
}

priority_queue<int, vector<int>, greater<int> > q;

void unlock(int x) {
    while (x) {
        if (locked[x]) {
            locked[x]=0;
            if (!du[x]) q.push(x);
        }
        int *t=&nxt[x];
        x=nxt[x];
        *t=0;
    }
}

void topsort() {
    for (int i=1; i<=n; i++)
        if (du[i]==0 && !locked[i]) q.push(i);
    while (!q.empty()) {
        int x=q.top();
        q.pop(), ans.push_back(x);
        unlock(head[x]);
        for (int y:E[x]) {
            du[y]--;
            if (du[y]==0 && !locked[y]) q.push(y);
        }
    }
}

void solve() {
    cin>>n;
    for (int i=1; i<=n; i++) e[i].clear(), E[i].clear();
    fill(du+1, du+n+1, 0);
    fill(nxt+1, nxt+n+1, 0);
    int flag=0;
    for (int i=1; i<=n; i++) {
        cin>>d[i];
        if (d[i]<0) d[i]=n+10, locked[i]=0;
        else locked[i]=1;
        if (d[i]==0) flag=1;
    }
    for (int i=1; i<n; i++) {
        int x, y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    if (flag) {
        cout<<-1<<endl;
        return;
    }
    dfs(1, 0, 1);
    ans.clear();
    topsort();
    if (ans.size()!=n) {
        cout<<-1<<endl;
        return;
    }
    for (int i:ans) cout<<i<<" ";
    cout<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while (T--) solve();
    return 0;
}
```