bzoj3306: 树（dfs序+倍增+线段树）

　　比较傻逼的一道题...

　　显然求子树最小值就是求出dfs序用线段树维护嘛

　　换根的时候树的形态不会改变，所以我们可以根据相对于根的位置分类讨论。

　　如果询问的x是根就直接输出整棵树的最小值。

　　如果询问的x是根在原树上的子节点，直接输出子树的最小值。

　　如果询问的x是根在原树上的祖先，那么就要输出整棵树去掉x在原树上那个包含根的子节点的子树的答案。

　　至于怎么求x在原树上那个包含根的子节点，可以用倍增。

　　但是我发现直接遍历x的子节点居然不会被卡，而且还跑到了第一页嘿嘿嘿

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

const int maxn=, inf=1e9;

struct poi{int too, pre;}e[maxn];

struct tjm{int sum;}tree[maxn<<];

int n, q, x, y, tot, tott, root;

int a[maxn], last[maxn], l[maxn], r[maxn], pos[maxn], d[maxn], f[maxn][];

char s[];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void add(int x, int y){e[++tot].too=y; e[tot].pre=last[x]; last[x]=tot;}

void dfs(int x)

{

    l[x]=++tott; pos[tott]=x; d[x]=d[f[x][]]+;

    for(int i=last[x];i;i=e[i].pre) f[e[i].too][]=x, dfs(e[i].too);

    r[x]=tott;

}

inline int min(int a, int b) {return a<b?a:b;}

inline void up(int x) {tree[x].sum=min(tree[x<<].sum, tree[x<<|].sum);}

void build(int x, int l, int r)

{

    if(l==r) {tree[x].sum=pos[l]?a[pos[l]]:inf; return;}

    int mid=(l+r)>>;

    build(x<<, l, mid); build(x<<|, mid+, r);

    up(x);

}

void update(int x, int l, int r, int cx, int delta)

{

    if(l==r) {tree[x].sum=delta; return;}

    int mid=(l+r)>>;

    if(cx<=mid) update(x<<, l, mid, cx, delta);

    else update(x<<|, mid+, r, cx, delta);

    up(x);

}

int query(int x, int l, int r, int cl, int cr)

{

    if(cl>cr) return inf;

    if(cl<=l && r<=cr) return tree[x].sum;

    int mid=(l+r)>>, ans=inf;

    if(cl<=mid) ans=query(x<<, l, mid, cl, cr);

    if(cr>mid) ans=min(ans, query(x<<|, mid+, r, cl, cr));

    return ans;

}

inline int solve(int x)

{

    if(x==root) return tree[].sum;

    if(l[x]>l[root] || r[x]<l[root]) return query(, , n, l[x], r[x]);

    int now=root;

    for(int i=;i>=;i--) if(d[f[now][i]]>x) now=f[now][i];

    return min(query(, , n, , l[now]-), query(, , n, r[now]+, n));

}

int main()

{

    read(n); read(q);

    for(int i=;i<=n;i++)

    {

        read(x); read(a[i]);

        if(x) add(x, i);

    }

    dfs(root=); build(, , n);

    for(int j=;j<=;j++) for(int i=;i<=n;i++) f[i][j]=f[f[i][j-]][j-];

    for(int i=;i<=q;i++)

    {

        scanf("%s", s+);

        if(s[]=='V') read(x), read(y), update(, , n, l[x], y);

        else if(s[]=='E') read(root);

        else read(x), printf("%d\n", solve(x));

    }

}

bzoj3306: 树（dfs序+倍增+线段树）的相关教程结束。