大體題意：

給你一顆樹，ri 為以當前結點為根的最小子樹上的權值（單點），每個點有固定的權值vi，每個點的權值都不一樣，每次你必須優先訪問ri最小的，然后刪掉，然后重新計算ri，求這個刪除點的路徑？

思路：

比賽中只想到了用dp 記錄某個點的最小權值，然后一直跳下去，然后在回來更新dp

這樣肯定是超時的。因為回來更新太慢了。

其實沒必要用dp記錄最小權值。

直接給這棵樹 進行dfs序列重新標號，使得每一個完整子樹都是連續的，這樣就可以用線段樹求出最小權值。

在用一個pos[i]數組表示哪個 點的權值是i，這樣就可以一直跳下去，然后刪點，不把這個子樹刪除干凈 不用回溯。

這樣每個結點只訪問了一次。

再加上線段樹求最小值。

復雜度是nlogn

因為各個點的權值不同，但又很大，直接拿一個unorderedmap進行離散化就好了。

#include <cstdio>#include <cstring>#include <algorithm>#include <unordered_map>#define Siz(x) (int)x.size()#define MIN(a,b) ((a)<(b)?(a):(b))using namespace std;const int maxn = 1e5 + 7;const int inf = 0x3f3f3f3f;vector<int>g[maxn];unordered_map<int,int>Hash;int w[maxn], id[maxn], li[maxn], ri[maxn], Min[maxn << 2], pos[maxn];int cnt = 0, sp = 0, n;struct Node{    int v;    int id;    bool Operator < (const Node& rhs) const {        return v < rhs.v;    }}p[maxn];void pushup(int o){    Min[o] = MIN(Min[o<<1],Min[o<<1|1]);}void build(int l,int r,int o){    if (l == r){        Min[o] = Hash[w[id[l] ]];        return ;    }    int m = l+r >> 1;    build(l,m,o<<1);    build(m+1,r, o<<1|1);    pushup(o);}void update(int p,int k,int l,int r,int o){    if (l == r){        Min[o] = k;        return;    }    int m = l+r>>1;    if (p <= m) update(p,k,l,m,o<<1);    else update(p,k,m+1,r,o<<1|1);    pushup(o);}int query(int L,int R,int l,int r,int o){    if (L <= l && r <= R){        return Min[o];    }    int m = l+r>>1;    int ans = inf;    if (L <= m) ans = MIN(ans,query(L,R,l,m,o<<1));    if (m < R) ans = MIN(ans,query(L,R,m+1,r,o<<1|1));    return ans;}void dfs(int cur,int PRe){    li[cur] = ++cnt;    id[cnt] = cur;    for (int i = 0; i < Siz(g[cur]); ++i){        int v = g[cur][i];        if (v != pre){            dfs(v,cur);        }    }    ri[cur] = cnt;}void print(int cur){    if (sp++) printf(" ");    printf("%d",cur);}void dd(int cur){    int L = li[cur];    int R = ri[cur];    while(1) {        int t;        if (L+1 <= R) t = query(L+1,R,1,n,1);        if ( L+1 > R || t == inf ){            print(cur);            update(L, inf,1,n,1);            return;        }        else {            int nxt = pos[t];            dd(nxt);        }    }}int main(){    while(~scanf("%d",&n)){        Hash.clear();        for (int i = 1; i <= n; ++i){            g[i].clear();        }        cnt = sp = 0;        for (int i = 1; i < n; ++i){            int u;            scanf("%d",&u);            g[u].push_back(i+1);        }        for (int i = 1; i <= n; ++i){            scanf("%d",w+i);            p[i].v = w[i];            p[i].id = i;        }        sort(p+1,p+n+1);        for (int i = 1; i <= n; ++i){            Hash[p[i].v ] = i;            pos[i] = p[i].id;        }        dfs(1,-1);        build(1,n,1);        dd(1);        puts("");    }    return 0;}/**54 4 1 13 5 2 1 4**/