dwjshift's Blog

bzoj3083 遥远的国度

| Comments

原文发表时间:2014-09-05
先暂时无视掉换根。如果只有树上路径操作的话就是树剖sb题,只有子树操作的话就是dfs序sb题。但是这题两者都有,怎么办呢?实际上,树剖的时候在同一个子树中的节点也是在一个连续的区间中的,就是说,树剖其实也是dfs序。那么后两个操作就解决了。
接着就是换根。画个图yy一下就能发现,换根并不会影响所有节点的子树。我们实现的时候不需要改变树的形态,先随便取一个点作为根,查询/修改时只要分以下三种情况讨论一下即可:
1、u就是root,那么就直接输出全部节点的min。
2、lca(u,root)不为u,那么u的子树没有改变,答案就是u的子树中的最小值。
3、lca(u,root)是u,假设v为u的儿子且root在v的子树内,答案就是u的子树的补集,即dfs序中的。这里v直接用树剖往上跳就能在找到了。
时间复杂度
另外这题似乎是不会爆32位无符号整型的……反正我直接用int也A了……

code

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (i=x; i<=y; ++i)
#define repe(i,x) for (edge *i=first[x]; i; i=i->next)
#define lc now<<1
#define rc now<<1|1
#define mid ((l+r)>>1)
using namespace std;
  
int n,m,i,a[100100],u,v,w,root,s[100100],dep[100100],son[100100],fa[100100],top[100100],
cnt,l[100100],r[100100],ql,qr,minv[262144],tag[262144],type,ans;
struct edge
{
    int v;
    edge *next;
} pool[200100],*tp=pool,*first[100100];
  
void dfs(int x)
{
    s[x]=1;
    repe(i,x)
        if (i->v!=fa[x])
        {
            fa[i->v]=x;
            dep[i->v]=dep[x]+1;
            dfs(i->v);
            if (s[i->v]>s[son[x]])
                son[x]=i->v;
            s[x]+=s[i->v];
        }
}
  
inline void push_down(int now)
{
    if (!tag[now])
        return;
    minv[lc]=minv[rc]=tag[lc]=tag[rc]=tag[now];
    tag[now]=0;
}
  
void modify(int now,int l,int r)
{
    if (ql<=l && qr>=r)
    {
        minv[now]=tag[now]=w;
        return;
    }
    push_down(now);
    if (ql<=mid)
        modify(lc,l,mid);
    if (qr>mid)
        modify(rc,mid+1,r);
    minv[now]=min(minv[lc],minv[rc]);
}
  
void dfs_(int x)
{
    ql=qr=l[x]=r[x]=++cnt,w=a[x],modify(1,1,n);
    if (s[x]==1)
        return;
    top[son[x]]=top[x];
    dfs_(son[x]);
    repe(i,x)
        if (i->v!=fa[x] && i->v!=son[x])
        {
            top[i->v]=i->v;
            dfs_(i->v);
        }
    r[x]=cnt;
}
  
void query(int now,int l,int r)
{
    if (ql<=l && qr>=r)
    {
        ans=min(ans,minv[now]);
        return;
    }
    push_down(now);
    if (ql<=mid)
        query(lc,l,mid);
    if (qr>mid)
        query(rc,mid+1,r);
}
  
int lca(int u,int v)
{
    while (top[u]!=top[v])
    {
        if (dep[top[u]]<dep[top[v]])
            swap(u,v);
        if (type==2)
            ql=l[top[u]],qr=l[u],modify(1,1,n);
        u=fa[top[u]];
    }
    if (dep[u]>dep[v])
        swap(u,v);
    if (type==2)
        ql=l[u],qr=l[v],modify(1,1,n);
    return u;
}
  
int query(int u,int v)
{
    while (dep[fa[top[u]]]>dep[v])
        u=fa[top[u]];
    if (fa[top[u]]==v)
        return top[u];
    return son[v];
}
  
int main()
{
    scanf("%d%d",&n,&m);
    repu(i,1,n-1)
    {
        scanf("%d%d",&u,&v);
        tp->v=v,tp->next=first[u],first[u]=tp++;
        tp->v=u,tp->next=first[v],first[v]=tp++;
    }
    repu(i,1,n)
        scanf("%d",&a[i]);
    dfs(1);
    dfs_(top[1]=1);
    scanf("%d",&root);
    while (m--)
    {
        scanf("%d",&type);
        if (type==1)
            scanf("%d",&root);
        if (type==2)
        {
            scanf("%d%d%d",&u,&v,&w);
            lca(u,v);
        }
        if (type==3)
        {
            scanf("%d",&u);
            if (u==root)
                printf("%d\n",minv[1]);
            else
            {
                ans=2147483647;
                if (lca(u,root)!=u)
                    ql=l[u],qr=r[u],query(1,1,n);
                else
                {
                    v=query(root,u);
                    if (l[v]>1)
                        ql=1,qr=l[v]-1,query(1,1,n);
                    if (r[v]<n)
                        ql=r[v]+1,qr=n,query(1,1,n);
                }
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

Comments

comments powered by Disqus