UOJ Logo SHYI的博客

博客

[POI2007]大都市meg 题解

2016-07-31 16:29:17 By SHYI

题目大意:有一棵树,最先每条边的权值是1,然后给出n+m-1个操作,操作有两种:1.询问一个点到根的路径上的权值和;2.将一条边的权值改为0.

思路:用dfs序将树化为序列,在dfs序中我们会保存节点i进入时间come[i]和出去时间leave[i],这两个数之间的区间即为其子树。询问实为前缀和,可用树状数组记录。修改只会影响其子树(即区间),其他部分并不会改变(+1-1抵消了)。

代码:

#include<cstdio>
#include<iostream>
#define M 300000 
using namespace std;

int n,m,cnt,dfn,to[M],next[M],head[M],c[M],come[M],leave[M];

int read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs(int x)
{
     come[x]=++dfn;
     for (int i=head[x];i;i=next[i]) dfs(to[i]);
     leave[x]=dfn;
}

void add(int x,int y)
{
     for (;x<=n;x+=x&-x) c[x]+=y;
}

int sum(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=c[x];
    return ans;
}

int main()
{
    int i,j,x,y;
    n=read();
    for (i=1;i<n;i++) x=read(),y=read(),ins(x,y);
    dfs(1);
    m=read();
    for (i=2;i<=n;i++) add(come[i],1),add(leave[i]+1,-1);
    for (i=1;i<n+m;i++)
    {
        char ch=getchar();
        while (ch<'A' || ch>'Z') ch=getchar();
        if (ch=='W') printf("%d\n",sum(come[read()]));
        else x=read(),y=read(),add(come[y],-1),add(leave[y]+1,1);
    }scanf("%d",&n);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。