首页 > 代码库 > 大都市 meg
大都市 meg
Description
在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。
昔日，乡下有依次编号为1..n的n个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。
随着时间的推移，越来越多的土路被改造成了公路。至今，Blue Mary还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了——所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。
Blue Mary想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在Blue Mary需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）
Input
第一行是一个数n.
以下n-1行，每行两个整数a，b（1<=a<b<=n），表示改造开始之前有一条土路连接着村庄a和村庄b.
以下一行包含一个整数m，表示Blue Mary曾经在改造期间送过m次信。
以下n+m-1行，每行有两种格式的若干信息，表示按时间先后发生过的n+m-1次事件:
若这行为 A a b(1<=a<b<=n),则表示城市a,b之间的土路被改成公路，保证不会重复；
若这行为 W a, 则表示Blue Mary曾经从比特堡送信到村庄a。
输入保证：
对于70％数据：1<=n,m<=50
对于所有数据：1<=n,m<=100000;
Output
有m行，每行包含一个整数，表示对应的某次送信时经过的土路数目。
Sample Input
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
Sample Output
2
1
0
1
题解:
因为它是一棵树，所以利用树的性质即可，用两个bfs维护dist[]数组就可以了。
一个用来初始化，另一个用来修改。注意以下几点：
1.由于一开始所有的边都是土路，所以每个点的dist就是它到根节点的最短路。
2.每次修改一条边实际上就是把编号大的那个节点和它的子树上的节点的dist-1就可以了。
代码如下：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 using namespace std;
9 int n,m;
10 int gi()
11 {
12 int ans=0,f=1;
13 char i=getchar();
14 while(i<‘0‘||i>‘9‘){if(i==‘-‘)f=-1;i=getchar();}
15 while(i>=‘0‘&&i<=‘9‘){ans=ans*10+i-‘0‘;i=getchar();}
16 return ans*f;
17 }
18 struct node
19 {
20 int next,to;
21 }edge[100005];
22 int head[100005],size;
23 void putin(int from,int to)
24 {
25 size++;
26 edge[size].to=to;
27 edge[size].next=head[from];
28 head[from]=size;
29 }
30 int dist[100005];
31 void bfs(int r)
32 {
33 int i;
34 memset(dist,127/3,sizeof(dist));
35 queue<int>mem;
36 mem.push(r);
37 dist[r]=0;
38 while(!mem.empty())
39 {
40 int x=mem.front();mem.pop();
41 for(i=head[x];i!=-1;i=edge[i].next)
42 {
43 int y=edge[i].to;
44 dist[y]=dist[x]+1;
45 mem.push(y);
46 }
47 }
48 }
49 void change(int r)
50 {
51 int i;
52 queue<int>mem;
53 mem.push(r);
54 dist[r]--;
55 while(!mem.empty())
56 {
57 int x=mem.front();mem.pop();
58 for(i=head[x];i!=-1;i=edge[i].next)
59 {
60 int y=edge[i].to;
61 dist[y]--;
62 mem.push(y);
63 }
64 }
65 }
66 int main()
67 {
68 freopen("meg.in","r",stdin);
69 freopen("meg.out","w",stdout);
70 int i,j;
71 n=gi();
72 memset(head,-1,sizeof(head));
73 for(i=1;i<n;i++)
74 {
75 int from=gi(),to=gi();
76 if(from>to)swap(from,to);
77 putin(from,to);
78 }
79 m=gi();
80 bfs(1);