树剖换个根(被lxl嘲笑祭)

· · 题解

树剖换根啊,,zz的我zz的请教lxl,大师拍案大笑,不语,少顷,我大呼:"我是zz!"呵呵,太尴尬了...

主要就是第3种嘛,其实也很好想

找到路径u->rt上的u的直系儿子v,

就会发现rt为根时,u子树覆盖不到的地方是v及v的子树

那么我们就可以把那一段抠出来,因为子树的重儿子序一定是连续的嘛!之后计算剩余部分就可以了

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N=1e5+5;
int rt,n,m,dep[N],f[N],num[N],son[N],top[N],tpos[N],pre[N],tot,cnt,bj[N<<2],minn[N<<2],first[N],w[N];
struct edge{int nt,to;}e[N<<1];
void add(int u,int v){e[++cnt]=(edge){first[u],v};first[u]=cnt;}
void dfs1(int u,int fa)
{
    num[u]=1;
    for(int i=first[u];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v==fa) continue;
        f[v]=u,dep[v]=dep[u]+1;
        dfs1(v,u);
        num[u]+=num[v];
        if(num[v]>num[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp,tpos[u]=++tot,pre[tot]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int i=first[u];i;i=e[i].nt)
    {
        int v=e[i].to;
        if(v==f[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void pushup(int rt){minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);}
void pushdown(int rt)
{
    if(bj[rt])
    {
        bj[rt<<1]=bj[rt<<1|1]=bj[rt];
        minn[rt<<1]=minn[rt<<1|1]=bj[rt];
        bj[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        minn[rt]=w[pre[l]];
        return;
    }
    int m=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
void modify(int l,int r,int rt,int nowl,int nowr,int c)
{
    if(nowl<=l&&r<=nowr)
    {
        minn[rt]=bj[rt]=c;
        return;
    }
    int m=(l+r)>>1;
    pushdown(rt);
    if(nowl<=m) modify(lson,nowl,nowr,c);
    if(nowr>m) modify(rson,nowl,nowr,c);
    pushup(rt);
}
int query(int l,int r,int rt,int nowl,int nowr)
{
    if(nowl<=l&&r<=nowr) return minn[rt];
    int m=(l+r)>>1,ans=INF;
    pushdown(rt);
    if(nowl<=m) ans=min(ans,query(lson,nowl,nowr));
    if(nowr>m) ans=min(ans,query(rson,nowl,nowr));
    pushup(rt);
    return ans;
}
void chain_modify(int u,int v,int w)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        modify(1,n,1,tpos[top[u]],tpos[u],w);
        u=f[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    modify(1,n,1,tpos[u],tpos[v],w);
}
int find(int u)
{
    if(u==rt) return -1;
    if(tpos[u]>=tpos[rt]||tpos[u]+num[u]-1<tpos[rt]) return 0;
    int now=rt;
    while(top[now]!=top[u])
    {
        if(f[top[now]]==u) return top[now];
        now=f[top[now]];
    }
    return son[u];
}
int tree_query(int u)
{
    int bo=find(u);
    if(bo==-1) return minn[1];
    if(bo==0) return query(1,n,1,tpos[u],tpos[u]+num[u]-1);
    else
    {
        int ans=query(1,n,1,1,tpos[bo]-1);
        if(tpos[bo]+num[bo]-1!=n) ans=min(ans,query(1,n,1,tpos[bo]+num[bo],n));
        return ans;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n;++i) scanf("%d",&w[i]);
    dfs1(1,0),dfs2(1,1),build(1,n,1);
    scanf("%d",&rt);
    for(int i=1,bo,u,v,w;i<=m;++i)
    {
        scanf("%d",&bo);
        if(bo==1) scanf("%d",&rt);
        if(bo==2) scanf("%d%d%d",&u,&v,&w),chain_modify(u,v,w);
        if(bo==3) scanf("%d",&u),printf("%d\n",tree_query(u));
    }
    return 0;
}