BZOJ 3083 遙遠的國度 DFS序 樹鏈剖分

BZOJ 3083 遙遠的國度 DFS序 樹鏈剖分

題目大意：給定一棵有根樹，每個點有一個權值，提供三種操作：

1.將x節點變為根節點

2.將x到y路徑上的點的權值全部改為v

3.詢問x的子樹中點權的最小值

樹鏈剖分沒商量！不過由於是查詢子樹的最小權值，所以我們選擇DFS序剖分，而不是先前的輕重鏈剖分

即每個節點第一個遍歷到的兒子是親兒子 重標號就是DFS序

然後就好辦了 換根的話不用真的換 只需要記錄當前的根節點 然後求解時分三種情況討論

1.root在x的子樹中但不為x 此時枚舉x的子節點y 若root在y的子樹中 則求子樹y的補集

2.root=x x是根節點 x的子樹就是整棵樹 此時直接輸出全集

3.root不在x的子樹中 此時直接輸出x的子樹的最小權值即可

很好寫的一道題，掛了一下午。。。。。RE了三遍，干掉三個BUG，然後發現原來是freopen沒刪。。。交上去還是WA，這時發現少討論第二種情況。。

最後寫完是4000-MS。。。 今天是腫了麼怎麼寫的這麼慘。。。

#include
#include
#include
#include
#define ls tree[p].lson
#define rs tree[p].rson
#define M 100100
using namespace std;
struct Tree{
    int num,mark;
    int lson,rson;
}tree[M<<1];
struct abcd{
    int to,next;
}table[M<<1];
int head[M],tot;
int n,m,root,treetot,f[M],fa[M],dpt[M],top[M],son[M],pos[M],last[M],posf[M],cnt;
void add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    int i,lastson=0;
    dpt[x]=dpt[fa[x]]+1;
    pos[x]=++cnt;
    if(son[fa[x]]==x)
        top[x]=top[fa[x]];
    else
    	top[x]=x;
    for(i=head[x];i;i=table[i].next)
    {
        if(table[i].to==fa[x])
            continue;
        fa[table[i].to]=x;
        if(!son[x])
            son[x]=table[i].to;
        lastson=table[i].to;
        dfs(table[i].to);
    }
    if(lastson)
		last[x]=last[lastson];
    else
        last[x]=pos[x];
}
void Build_Tree(int p,int x,int y)
{
    int mid=x+y>>1;
    if(x==y)
    {
        tree[p].num=posf[mid];
        return ;
    }
    ls=++treetot;rs=++treetot;
    Build_Tree(ls,x,mid);
    Build_Tree(rs,mid+1,y);
    tree[p].num=min(tree[ls].num,tree[rs].num);
}
void update(int p,int x,int y,int l,int r,int v)
{
    int mid=x+y>>1;
    if(x==l&&y==r)
    {
        tree[p].num=tree[p].mark=v;
        return ;
    }
    if(tree[p].mark)
    {
        tree[ls].num=tree[ls].mark=tree[p].mark;
        tree[rs].num=tree[rs].mark=tree[p].mark;
        tree[p].mark=0;
    }
    if(r<=mid) update(ls,x,mid,l,r,v);
    else if(l>mid) update(rs,mid+1,y,l,r,v);
    else update(ls,x,mid,l,mid,v),update(rs,mid+1,y,mid+1,r,v);
    tree[p].num=min(tree[ls].num,tree[rs].num);
}
void change(int x,int y,int z)
{
    int fx=top[x],fy=top[y];
    while(fx!=fy)
    {
        if(dpt[fx]>1;
    if(x==l&&y==r)
        return tree[p].num;
    if(tree[p].mark)
    {
        tree[ls].num=tree[ls].mark=tree[p].mark;
        tree[rs].num=tree[rs].mark=tree[p].mark;
        tree[p].mark=0;
    }
    if(r<=mid) return getans(ls,x,mid,l,r);
    else if(l>mid) return getans(rs,mid+1,y,l,r);
    else return min( getans(ls,x,mid,l,mid) , getans(rs,mid+1,y,mid+1,r) );
}
int query(int x)
{
	if(x==root)
    	return getans(0,1,n,1,n);
    if(pos[root]last[x])
        return getans(0,1,n,pos[x],last[x]);
    int i,re=0x7fffffff;
    for(i=head[x];i;i=table[i].next)
        if(pos[root]>=pos[table[i].to]&&pos[root]<=last[table[i].to]&&table[i].to!=fa[x])
            break;
    re=min(re,getans(0,1,n,1,pos[table[i].to]-1));
    if(last[table[i].to]!=n)
        re=min(re,getans(0,1,n,last[table[i].to]+1,n));
    return re;
}
int main()
{
    int i,x,y,z,p;
    cin>>n>>m;
    for(i=1;i>root;
    dfs(root);
    for(i=1;i<=n;i++)
        posf[pos[i]]=f[i];
    Build_Tree(0,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&p);
        if(p==1)
            scanf("%d",&root);
        else if(p==2)
            scanf("%d%d%d",&x,&y,&z),change(x,y,z);
        else
            scanf("%d",&x),printf("%d\n",query(x));
    }
}