[POI2007]MEG-Megalopolis (树状数组,Dfs序)

题目描述

## Solution
这道题考试的时候竟然没有仔细想,结果只拿了暴力分...
其实就是一个 DFS序+树状数组。

我们先把用 DFS 把它变成一个序列,同时记录它们的 \(siz\)。

那么我们每一次连一条边之后就是对它的子树产生影响。

在树状数组里面维护就好了。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=250008;

struct sj{

	int to;

	int next;

}a[maxn*2];

int head[maxn],size;

int n,m;

void add1(int x,int y)

{

	a[++size].to=y;

	a[size].next=head[x];

	head[x]=size;

}

int id[maxn],tot;

int siz[maxn],ans[maxn];

void dfs(int x)

{

	id[x]=++tot;

	siz[x]=1;

	for(int i=head[x];i;i=a[i].next)

	{

		int tt=a[i].to;

		if(!siz[tt])

		{

			ans[tt]=ans[x]+1;

			dfs(tt);

			siz[x]+=siz[tt];

		}

	}

}

int c[maxn];

int lowbit(int x)

{return x&(-x);}

void add(int x,int z)

{for(int i=x;i<=n;i+=lowbit(i))c[i]+=z;}

int check(int x)

{

    int sum=0;

    for(int i=x;i>=1;i-=lowbit(i))

      sum+=c[i];

    return sum;

}

int main()

{

	scanf("%d",&n);

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

	{int x,y; scanf("%d%d",&x,&y);add1(x,y); add1(y,x);}

	dfs(1);

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

	add(id[i],0);

	scanf("%d",&m);

	for(int i=1;i<=m+n-1;i++)

	{

		int x,y;char ch; cin>>ch;

		if(ch=='A')

		{

			scanf("%d%d",&x,&y);

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

			add(id[x],1);

			add(id[x]+siz[x],-1);

		}

		if(ch=='W')

		scanf("%d",&x),

			cout<<ans[x]-check(id[x])<<endl;

	}

}

巴特西

[POI2007]MEG-Megalopolis (树状数组,Dfs序)

题目描述

代码

最新文章

热门文章