ICPCCamp2017 Day 5 E HDRF（DFS序列 + 线段树 + 离散化）

大体题意：

给你一颗树，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**/