[bzoj1103][POI2007]大都市meg_dfs序_树状数组

大都市meg bzoj-1103 POI-2007

题目大意：给定一颗n个点的树，m次操作。将一条路的边权更改成0；查询一个点到根节点的点权和。开始的时候所有边的边权都是1。

注释：$1\le n,m\le 2.5\cdot 10^5$。

---

想法：我们先拉出dfs序。其实严格来讲是出栈入栈序，就是每个点在序上出现两次的那个。

开始的时候入栈时的点权是1，出栈是-1。修改就是把出栈入栈都改成0。然后用树状数组查询前缀和即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 250010

using namespace std;

int tree[N<<1],val[N<<1],head[N],to[N<<1],nxt[N<<1],tot,cnt;

int dic[N<<1];

struct Node

{

	int x,y;

}a[N];

inline int lowbit(int x) {return x&(-x);}

void fix(int x,int delta)

{

	for(int i=x;i<=cnt+1;i+=lowbit(i))

	{

		// puts("fix");

		tree[i]+=delta;

	}

}

int query(int x)

{

	int ans=0;

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

	{

		// puts("query");

		ans+=tree[i];

	}

	return ans;

}

inline void add(int x,int y)

{

	to[++tot]=y;

	nxt[tot]=head[x];

	head[x]=tot;

}

void dfs(int pos,int fa)

{

	// if(a[pos].x) puts("FUCK");

	dic[++cnt]=pos;

	// cnt++;

	val[cnt]=1;

	a[pos].x=cnt;

	for(int i=head[pos];i;i=nxt[i])

	{

		if(to[i]==fa) continue;

		dfs(to[i],pos);

	}

	dic[++cnt]=pos;

	// cnt++;

	val[cnt]=-1;

	a[pos].y=cnt;

}

int main()

{

	int n; cin >> n ;

	int x,y;

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

	{

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

		add(x,y); add(y,x);

	}

	dfs(1,0);

	val[1]=0;

	val[cnt]=0;

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

	{

		fix(i,val[i]);

	}

	// printf("Gun %d\n",cnt);

	// for(int i=1;i<=cnt;i++)

	// {

	// 	printf("Shit %d\n",dic[i]);

	// }

	// puts("--------------------------------------");

	int m; cin >> m ;

	char opt[10];

	// for(int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].y);

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

	{

		// printf("Fuck %d\n",i);

		scanf("%s",opt+1);

		if(opt[1]=='A')

		{

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

			if(x>y) swap(x,y);

			fix(a[y].x,-1);

			fix(a[y].y,1);

		}

		else

		{

			scanf("%d",&x);

			// printf("%d\n",query(3));

			printf("%d\n",query(a[x].x));

		}

	}

	return 0;

}

小结：简单题。