八中链接 http://www.zybbs.org/JudgeOnline/problem.php?id=1103
原题链接 http://main.edu.pl/en/archive/oi/14/meg
题目大意：给你一棵树（仔细揣摩题目描述，是树），边有权（1或0），每个询问问从1到x的路径上权值和是多少。
看完我就在想LCT乱搞……然后发现LCT有点高射炮打蚊子了。后来发现这个题可以线性维护DFS序列来做，用线段树。
（PS：其实我写树状数组…………）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define mn 250002
#define lowbit(x) (x)&(-x)
using namespace std;
pair<int,int> pos[mn];
int n,m,a,b,node=0,s[mn*2];
char sym[2];
bool vis[mn];
struct EDGE{
int pnt;
EDGE *pre;
EDGE(){}
EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
}Edge[mn*2],*SP=Edge,*edge[mn];
inline void addedge(int a,int b){
edge[a]=new(++SP)EDGE(b,edge[a]);
edge[b]=new(++SP)EDGE(a,edge[b]);
}
void Modify(int x,int val){
while(x<=n) s[x]+=val,x+=lowbit(x);
}
int Query(int x){
int sum=0;
while(x>0) sum+=s[x],x-=lowbit(x);
return sum;
}
void dfs(int x){
pos[x].first=++node;
Modify(node,1);
vis[x]=true;
for(EDGE *j=edge[x];j;j=j->pre)
if(!vis[j->pnt]) dfs(j->pnt);
pos[x].second=++node;
Modify(node,-1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
}
n<<=1;
dfs(1);
scanf("%d",&m);
while(m){
scanf("%s",sym);
if(sym[0]=='W'){
scanf("%d",&a);
printf("%d\n",Query(pos[a].first)-1);
m--;
}else{
scanf("%d%d",&a,&b);
Modify(pos[b].first,-1);
Modify(pos[b].second,1);
}
}
return 0;
}
