【BZOJ-3306】树线段树 + DFS序

3306: 树

Time Limit: 10 Sec Memory Limit: 256 MB
Submit:
792 Solved: 262
[Submit][Status][Discuss]

Description

给定一棵大小为 n 的有根点权树,支持以下操作:

　　• 换根
　　• 修改点权
　• 查询子树最小值

Input

　　第一行两个整数 n, Q
,分别表示树的大小和操作数。
　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如果f =
0,那么i为根。输入数据保证只有i = 1时,f = 0。
　　接下来 m 行,为以下格式中的一种:
　　• V x y表示把点x的权改为y

　　• E x 表示把有根树的根改为点 x
　　• Q x 表示查询点 x 的子树最小值

Output

　　对于每个 Q
,输出子树最小值。

Sample Input

3 7
0 1
1 2
1 3
Q
1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1

Sample Output

1
2
3
4

HINT

　　对于 100% 的数据:n, Q ≤ 10^5。

Source

Solution

有道很类似的题目，不过是树链修改

那道题去要树链剖分，而这里只需要线段树维护一下DFS序即可

先以1为根做DFS和建线段树维护dfs序

换根操作只需要讨论一下：

若root=x，那么显然查询全树min

若LCA(root，x）！=x，那么显然毫无影响

若LCA（root，x）==x，那么发现对答案产生了影响，除了x-->root的那个子树，其余都变成了x的子树，那么我们倍增出那个不属于的子树中最接近x的节点，然后统计不包含这棵子树的答案即可

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 100010

int N,Q,val[MAXN];

struct EdgeNode{int next,to;}edge[MAXN<<];

int head[MAXN],cnt;

void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void InsertEdge(int u,int v) {if (u==) return; AddEdge(u,v); AddEdge(v,u);}

int pl[MAXN],dfn,pr[MAXN],dfsn[MAXN],deep[MAXN],father[MAXN][],root;

void DFS(int now,int last)

{

    pl[now]=++dfn; dfsn[dfn]=now;

    for (int i=; i<=; i++)

        if (deep[now]>=(<<i))

            father[now][i]=father[father[now][i-]][i-];

        else

            break;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=last)

            {

                deep[edge[i].to]=deep[now]+;

                father[edge[i].to][]=now;

                DFS(edge[i].to,now);

            }

    pr[now]=dfn;

}

int LCA(int x,int y)

{

    if (deep[x]<deep[y]) swap(x,y);

    int dd=deep[x]-deep[y];

    for (int i=; i<=; i++)

        if (dd&(<<i)) x=father[x][i];

    for (int i=; i>=; i--)

        if (father[x][i]!=father[y][i])

            x=father[x][i],y=father[y][i];

    if (x==y) return x; else return father[x][];

}

struct SegmentTreeNode{int l,r,minn;}tree[MAXN<<];

inline void Update(int now) {tree[now].minn=min(tree[now<<].minn,tree[now<<|].minn);}

void BuildTree(int now,int l,int r)

{

    tree[now].l=l; tree[now].r=r;

    if (l==r) {tree[now].minn=val[dfsn[l]]; return;}

    int mid=(l+r)>>;

    BuildTree(now<<,l,mid);

    BuildTree(now<<|,mid+,r);

    Update(now);

}

void Change(int now,int pos,int D)

{

    int l=tree[now].l,r=tree[now].r;

    if (l==r) {tree[now].minn=D; return;}

    int mid=(l+r)>>;

    if (pos<=mid) Change(now<<,pos,D);

        else Change(now<<|,pos,D);

    Update(now);

}

int Query(int now,int L,int R)

{

    if (R<L) return 0x7fffffff;

    int l=tree[now].l,r=tree[now].r;

    if (L==l && R==r) return tree[now].minn;

    int mid=(l+r)>>,re=0x7fffffff;

    if (R<=mid) return Query(now<<,L,R);

        else if (L>mid) return Query(now<<|,L,R);

            else return min(Query(now<<,L,mid),Query(now<<|,mid+,R));

    return re;

}

void ChangeRoot(int x)  {root=x;}

int GetAns(int x)

{

    int lca=LCA(root,x);

    if (x==root) return Query(,,N);

    if (pl[x]<=pl[root] && pr[x]>=pr[root])

        {

            int dd=deep[root]-deep[x]-,y=root;

            for (int i=; i<=; i++)

                if (dd&(<<i)) y=father[y][i];

            return min(Query(,,pl[y]-),Query(,pr[y]+,dfn));

        }

    return Query(,pl[x],pr[x]);

}

int main()

{

    N=read(); Q=read();

    for (int fa,i=; i<=N; i++) fa=read(),InsertEdge(fa,i),val[i]=read();

    DFS(,);  root=;

    BuildTree(,,dfn);

    while (Q--)

        {

            char opt[]; scanf("%s",opt+);

            int x,y;

            switch (opt[])

                {

                    case 'V' : x=read(),y=read(); Change(,pl[x],y); break;

                    case 'E' : x=read(); ChangeRoot(x); break;

                    case 'Q' : x=read(); printf("%d\n",GetAns(x)); break;

                }

        }

    return ;

}