BZOJ 1103 大都市（DFS序+树状数组+差分数组/树链剖分）

发表于 |
字数统计: 1,121字 | 阅读时长 ≈ 5min

大都市

问题描述

在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了。
不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为1..n的n个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。

另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。随着时间的推移，越来越多的土路被改造成了公路。至今，Blue Mary还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了——所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。
Blue Mary想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.
现在Blue Mary需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）

输入格式

　第一行是一个数n(1 < = n < = 2 50000).
以下n-1行，每行两个整数a，b（1 < =a < b<=n) 以下一行包含一个整数m（1 < = m < = 2 50000），表示Blue Mary曾经在改造期间送过m次信。
以下n+m-1行，每行有两种格式的若干信息，表示按时间先后发生过的n+m-1次事件:若这行为 A a b，表示道路a b被改成了公路。若这行为 W a, 则表示Blue Mary曾经从比特堡送信到村庄a。

输出格式

有m行，每行包含一个整数，表示对应的某次送信时经过的土路数目。

样例输入

5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3

样例输出

2
1
0
1

此题用树链剖分就是模板题了，但是效率当然不如下面的做法高。

将每一条边记录到儿子上，土路的点权为0，公路为1，那么询问就是从根到某点经过的点权为0的点数，显然等于点数-点权为1的点数，即点数-点权和。

考虑dfs序，那么当一条路被改成公路时，他所有子节点的答案都减了1，那么由于dfs序是连续的区间，相当于这一段区间的点权都加了1，那么用差分数组维护即可，考虑到询问次数多，用树状数组维护差分数组。查询就是对应DFS序的进入时间在差分数组中的前缀和。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#define N 250005
#define M 500005
using namespace std;
int n,m,C[N];
int TOT,LA[N],NE[M],EN[M];
int L[N],R[N],dep[N],VT;
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x,int f)
{
	L[x]=++VT;
	dep[x]=dep[f]+1;
	for(int i=LA[x];i;i=NE[i])
	if(EN[i]!=f)DFS(EN[i],x);
	R[x]=VT;
}
void MD(int x,int d)
{for(int i=x;i<=n;i+=(i&-i))C[i]+=d;}
int GS(int x)
{
	int i,sum=0;
	for(i=x;i>0;i-=(i&-i))sum+=C[i];
	return sum;
}
int main_main()
{
	int i,j,x,y;
	char c;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
	}
	DFS(1,0);
	scanf("%d",&m);
	for(i=1;i<=n+m-1;i++)
	{
		scanf("\n%c",&c);
		if(c=='A')
		{
			scanf("%d%d",&x,&y);
			if(dep[x]<dep[y])x^=y^=x^=y;
			MD(L[x],1);MD(R[x]+1,-1);
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",dep[x]-1-GS(L[x]));
		}
	}
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}