题意：给定点数n<=300000的一棵树，然后初始时每条边权值为1，接下来按照时间点先后顺序的n+m-1个操作，
操作有两种：
1.A a b 把a到b的边权改为0
2.W u 求1号点到u号点的路径权值和
思路：如果现在把题目简化为是在一条直线上的操作，每次在中间删除相邻边权值或者查询某个点到1号点的权值和
我们很容易想把询问离线，然后从1->n扫描1遍，然后用一个树状数组维护前缀和即可。。
到了本题利用dfs序显然就可以转化成线性模型，
具体的话
做到点u，
如果有一个操作1在(u, fa[u])的边，时间为t，那么在t时间点删除一个点
如果有一个操作2在u点，时间为t，那么就等价于查询1~u路径上的点数-t时间内删除的点数
回溯时把操作还原
code(stl)：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#define x first
#define y second
#define M0(x) memset(x, 0, sizeof(x))
#define vii vector<int>::iterator
#define vpi vector<pair<int, int> >::iterator
#define Inf 0x7fffffff
using namespace std;
typedef pair<int, int> pii;
const int maxn = ;
vector<int> e[maxn];
vector<pii> q[maxn];
int n, m, ans[maxn<<];
int pos[maxn<<]; inline void R(int &ret){
ret = ;
bool ok = ;
for( ; ;){
int c = getchar();
if (c >= '' && c <= '') ret = (ret << ) + (ret << ) + c - '', ok = ;
else if (ok) return;
}
} void init(){
int u, v;
// for (int i = 1; i <= n; ++i) e[i].clear(), q[i].clear();
pii tmp;
for (int i = ; i < n; ++i)
R(u), R(v), e[u].push_back(v), e[v].push_back(u);
char op[];
R(m);
int nm = n + m - ;
int n1 = ;
for (int i = ; i <= nm; ++i){
scanf("%s", op);
if (op[] == 'A') ++n1;
tmp.x = i;
pos[i] = n1;
if (op[] == 'W')
R(u), tmp.y = -, q[u].push_back(tmp);
else {
R(u), R(v);
tmp.y = v, q[u].push_back(tmp);
tmp.y = u, q[v].push_back(tmp);
}
}
// cout << n1 << endl;
} int vis[maxn], s[maxn], dep[maxn];
void update(int x,const int& v){
for (; x<=n; x += x&(-x)) s[x] += v;
} int query(int x){
int res = ;
for (; x>; x -= x&(-x)) res += s[x];
return res;
} int ss;
void dfs(const int& u){
vis[u] = ;
for (vpi it = q[u].begin(); it != q[u].end(); ++it)
if (it->y != - && vis[it->y]) update(pos[it->x], );
for (vpi it = q[u].begin(); it != q[u].end(); ++it)
if (it->y == -) ans[it->x] = dep[u] - query(pos[it->x]);
for (vii it = e[u].begin(); it != e[u].end(); ++it)
if (!vis[*it]) dep[*it] = dep[u] + , dfs(*it);
for (vpi it = q[u].begin(); it != q[u].end(); ++it)
if (it->y != - && dep[it->y] < dep[u]) update(pos[it->x], -);
} void solve(){
memset(ans, -, sizeof(int) * (n+m+));
memset(vis, , sizeof(int) * (n+));
memset(s, , sizeof(int) * (n+));
dep[] = ;
dfs();
int nm = n + m;
for (int i = ; i < nm; ++i)
if (ans[i] >= ) printf("%d\n", ans[i]);
} int main(){
while (scanf("%d", &n) != EOF){
init();
solve();
}
return ;
}
code（手写链表）：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#define M0(x) memset(x, 0, sizeof(x))
#define Inf 0x7fffffff
using namespace std;
const int maxn = ;
struct node{
int v, next;
} e[maxn * ];
struct qes{
int v, t, next;
} q[maxn << ];
int n, m, ans[maxn<<], last[maxn], lastq[maxn], tot, len;
int pos[maxn<<]; inline void R(int &ret){
ret = ;
bool ok = ;
for( ; ;){
int c = getchar();
if (c >= '' && c <= '') ret = (ret << ) + (ret << ) + c - '', ok = ;
else if (ok) return;
}
} inline void add(const int& u,const int& v){
e[tot] = (node){v, last[u]}, last[u] = tot++;
} inline void add_ask(const int& u,const int& v,const int& t){
q[len] = (qes){v, t, lastq[u]}, lastq[u] = len++;
} void init(){
int u, v;
memset(last, -, sizeof(last));
memset(lastq, -, sizeof(lastq));
len = tot = ;
for (int i = ; i < n; ++i)
R(u), R(v), add(u, v), add(v, u);
char op[];
R(m);
int nm = n + m - ;
int n1 = ;
for (int i = ; i <= nm; ++i){
scanf("%s", op);
if (op[] == 'A') ++n1;
pos[i] = n1;
if (op[] == 'W')
R(u), add_ask(u, -, i);
else {
R(u), R(v);
add_ask(u, v, i), add_ask(v, u, i);
}
}
// cout << n1 << endl;
} int vis[maxn], s[maxn], dep[maxn];
void update(int x,const int& v){
for (; x<=n; x += x&(-x)) s[x] += v;
} int query(int x){
int res = ;
for (; x>; x -= x&(-x)) res += s[x];
return res;
} void dfs(const int& u){
vis[u] = ;
for (int p = lastq[u]; ~p; p = q[p].next)
if (q[p].v != - && vis[q[p].v]) update(pos[q[p].t], );
for (int p = lastq[u]; ~p; p = q[p].next)
if (q[p].v == -) ans[q[p].t] = dep[u] - query(pos[q[p].t]);
for (int p = last[u]; ~p; p = e[p].next)
if (!vis[e[p].v]) dep[e[p].v] = dep[u] + , dfs(e[p].v);
for (int p = lastq[u]; ~p; p = q[p].next)
if (q[p].v != - && dep[q[p].v] < dep[u]) update(pos[q[p].t], -);
} void solve(){
memset(ans, -, sizeof(int) * (n+m+));
memset(vis, , sizeof(int) * (n+));
memset(s, , sizeof(int) * (n+));
dep[] = ;
dfs();
int nm = n + m;
for (int i = ; i < nm; ++i)
if (ans[i] >= ) printf("%d\n", ans[i]);
} int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
while (scanf("%d", &n) != EOF){
init();
solve();
}
return ;
}