BZOJ-3306: 树

Description

给定一棵大小为 n 的有根点权树,支持以下操作: • 换根 • 修改点权 • 查询子树最小值

分类讨论一下换根对于子树的范围的影响，找到对应dfs序的区间即可，注意当根在子树内时，对应的dfs序区间为全集除去该点到根的第一个儿子的dfs序区间。【对应区间包含其他儿子】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
const int inf=0x3f3f3f3f;
int n,m,root,w[N],in[N],out[N],tim;
int head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int dep[N],fa[N][20],Log[N];
int M,mi[N<<2];
void dfs(int x)
{
    in[x]=++tim; mi[M+tim]=w[x];
    for(int i=1;i<=Log[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=nxt[i])
    {
        dep[to[i]]=dep[x]+1;
        fa[to[i]][0]=x;
        dfs(to[i]);
    }
    out[x]=tim;
}
void fix(int x,int y)
{
    x+=M; mi[x]=y; x>>=1;
    while(x) mi[x]=min(mi[x<<1],mi[x<<1|1]),x>>=1;
}
int query(int l,int r)
{
    if(l>r) return inf; int re=inf;
    for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) re=min(re,mi[l^1]);
        if(r&1) re=min(re,mi[r^1]);
    }
    return re;
}
int find(int x,int y)
{
    for(int i=Log[y];~i;--i) if((y>>i)&1) x=fa[x][i];
    return x;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,x,y;
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&x,w+i);
        if(x==0) root=i;
        else add(x,i);
    }
    for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(M=1;M<=(n+1);M<<=1);
    dfs(root);
    for(i=M-1;i;--i) mi[i]=min(mi[i<<1],mi[i<<1|1]);
    char op[10];
    while(m--)
    {
        scanf("%s",op);
        switch(op[0])
        {
            case 'V': scanf("%d%d",&x,&y); fix(in[x],y); break;
            case 'E': scanf("%d",&root); break;
            case 'Q':
            {
                scanf("%d",&x);
                if(x==root) printf("%d\n",query(1,n));
                else if(in[x]<=in[root]&&out[root]<=out[x])
                {
                    y=find(root,dep[root]-dep[x]-1);
                    printf("%d\n",min(query(1,in[y]-1),query(out[y]+1,n)));
                }
                else printf("%d\n",query(in[x],out[x]));
                break;
            }
        }
    }
    return 0;
}