【BZOJ3306】树

2015.08.10 10:54 Mon | 39次阅读 | 旧日oi | 固定链接 | 源码

Description

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

题解

遥想今年年初看到这题我还觉得这题根本没法做呢……现在看来倒是挺水啦。
把树的dfs序搞出来,我们发现对于一个节点x来说,
如果根节点和x的lca不是x,那么dfs序就是st[x]-ed[x],否则的话说明根节点在x的子树中,那么dfs序就是v的补集,v是x的一个儿子,且v是根或根的祖先。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define N 100005
#define inf 0x3f3f3f3f
int n,Q,x,y,root,tim;
int w[N];
char s[2];
struct edge
{
    int to,next;
}e[N];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int mn[N<<2];
int rk[N],st[N],ed[N],tid[N];
int dep[N],fa[N][18];
void dfs(int u)
{
    for(int i=1;i<=17&&(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    st[u]=++tim;rk[tim]=u;
    for(int i=h[u];e[i].to;i=e[i].next)
    fa[e[i].to][0]=u,dep[e[i].to]=dep[u]+1,dfs(e[i].to);
    ed[u]=tim;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        mn[rt]=w[rk[l]];
        tid[l]=rt;
        return;
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void update(int p,int v)
{
    mn[p]=v;
    while(p>1)
    {
        p>>=1;
        mn[p]=min(mn[p<<1],mn[p<<1|1]);
    }
}
int get_lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y],i;
    for(i=0;t;i++)
    if(t&(1<<i)) x=fa[x][i],t^=(1<<i);
    if(x==y) return x;
    for(int i=17;i>=0;i--)
    if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int get_lca2(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y]-1;
    for(int i=17;i>=0;i--)
    if(t&(1<<i)) x=fa[x][i];
    return x;
}
int query(int l,int r,int rt,int L,int R)
{
    if(L>R) return inf;
    if(L==l&&R==r) return mn[rt];
    int mid=(l+r)>>1;
    if(L>mid) return query(rson,L,R);
    else if(R<=mid) return query(lson,L,R);
    else return min(query(lson,L,mid),query(rson,mid+1,R));
}
int get_ans(int x)
{
    if(x==root) return mn[1];
    int t=get_lca(x,root);
    if(t!=x) return query(1,n,1,st[x],ed[x]);
    else
    {
        t=get_lca2(root,x);
        return min(query(1,n,1,1,st[t]-1),query(1,n,1,ed[t]+1,n));
    }
}
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int main()
{
    //freopen("tt.in", "r", stdin);
    //freopen("me.out", "w", stdout);
    cin>>n>>Q;
    x=read();w[1]=read();
    for(int i=2;i<=n;i++)
    {
        x=read();w[i]=read();
        ae(x,i);
    }
    dfs(1);
    build(1,n,1);root=1;
    while(Q--)
    {
        scanf("%s",s);
        if(s[0]=='V')
        {
            x=read();y=read();
            update(tid[st[x]],y);
        }
        else if(s[0]=='E') root=read();
        else
        {
            x=read();
            printf("%d\n",get_ans(x));
        }
    }
}```