传送门：嘟嘟嘟
第一反应是树链剖分，但是太长懒得写，然后就想出了一个很不错的做法。
想一下，如果我们改一条边，那么影响的只有他的子树，只要先搞一个dfs序，为什么搞出这个呢？因为有一个性质：一个节点的子树在dfs序上是连续的，所以这道题就变成了一个单点查询，区间修改的线段树（树状数组）板子题。
然后我不到40分钟写完了，非说有的点TLE，debug了一个多点……现在想想，一般遇到这种情况，一定不是什么正经问题。然而当时的我并不这么想，以为线段树太慢了，改成差分+树状数组，各种优化，虽然在luogu卡了过去，然而内网却GG。
终于放弃，到网上找标程，发现写的几乎一模一样，就一行行比对……然后发现我为了省事儿读字母用了cin，按标称改成了scanf……结果最慢的点直接从900多ms变成了200多ms……然后内网秒过了……老子在此立flag：我，mrclr，如果再用cin，我就女装！
心路历程讲完了，发下代码吧
先是线段树的
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cctype>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 3e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) putchar('-'), x = -x;
if(x >= ) write(x / );
putchar(x % + '');
} int n;
vector<int> v[maxn]; int dis[maxn], dfsx[maxn], size[maxn], pos[maxn], cnt = ;
void dfs(const int& now)
{
dfsx[now] = ++cnt; pos[cnt] = now;
size[now] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
dis[v[now][i]] = dis[now] + ;
dfs(v[now][i]);
size[now] += size[v[now][i]];
}
return;
} int l[maxn << ], r[maxn << ], dis2[maxn << ], lazy[maxn << ];
void build(const int& L, const int& R, const int& now)
{
l[now] = L; r[now] = R;
if(L == R) {dis2[now] = dis[pos[L]]; return;}
int mid = (L + R) >> ;
build(L, mid, now << );
build(mid + , R, now << | );
dis2[now] = dis2[now << ] + dis2[now << | ];
}
void pushdown(const int& now)
{
if(lazy[now])
{
lazy[now << ] += lazy[now];
lazy[now << | ] += lazy[now];
dis2[now << ] -= lazy[now];
dis2[now << | ] -= lazy[now];
lazy[now] = ;
}
}
void update(const int& L, const int& R, const int& now)
{
if(!dis2[now]) return;
if(l[now] == L && r[now] == R)
{
dis2[now]--; lazy[now]++;
return;
}
pushdown(now);
int mid = (l[now] + r[now]) >> ;
if(R <= mid) update(L, R, now << );
else if(L > mid) update(L, R, now << | );
else {update(L, mid, now << ); update(mid + , R, now << | );}
}
int query(const int& id, const int& now)
{
if(!dis2[now]) return ;
if(l[now] == r[now]) return dis2[now];
pushdown(now);
int mid = (l[now] + r[now]) >> ;
if(id <= mid) return query(id, now << );
else return query(id, now << | );
} int main()
{
n = read();
for(int i = ; i < n; ++i)
{
int x = read(), y = read();
if(y < x) swap(x, y);
v[x].push_back(y);
}
dfs();
build(, cnt, );
int m = read();
char ch[];
for(int i = ; i < n + m; ++i)
{
scanf("%s", ch);
if(ch[] == 'W')
{
int x = read();
write(query(dfsx[x], )); enter;
}
else
{
int x = read(), y = read();
if(y > x) swap(x, y);
update(dfsx[x], dfsx[x] + size[x] - , );
}
}
return ;
}
然后又写了个差分+树状数组
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cctype>
using namespace std;
#define enter printf("\n")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 3e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) putchar('-'), x = -x;
if(x >= ) write(x / );
putchar(x % + '');
} int n;
vector<int> v[maxn]; int dis[maxn], dfsx[maxn], size[maxn], pos[maxn], cnt = ;
void dfs(const int& now)
{
dfsx[now] = ++cnt; pos[cnt] = now;
size[now] = ;
if(!v[now].size()) return;
for(int i = ; i < (int)v[now].size(); ++i)
{
dis[v[now][i]] = dis[now] + ;
dfs(v[now][i]);
size[now] += size[v[now][i]];
}
} int cf[maxn], c[maxn];
inline int lowbit(int x)
{
return x & -x;
}
void add(int pos, int x)
{
while(pos <= cnt)
{
c[pos] += x;
pos += lowbit(pos);
}
}
int sum(int pos)
{
int ret = ;
while(pos)
{
ret += c[pos];
pos -= lowbit(pos);
}
return ret;
} int main()
{
n = read();
for(int i = ; i < n; ++i)
{
int x = read(), y = read();
if(y < x) swap(x, y);
v[x].push_back(y);
}
dfs();
for(int i = ; i <= cnt; ++i) cf[i] = dis[pos[i]] - dis[pos[i - ]];
for(int i = ; i <= cnt; ++i) add(i, cf[i]);
int m = read();
char ch[];
for(int i = ; i < n + m; ++i)
{
scanf("%s", ch);
if(ch[] == 'W')
{
int x = read();
write(sum(dfsx[x])); enter;
}
else
{
int x = read(), y = read();
if(y > x) swap(x, y);
add(dfsx[x], -); add(dfsx[x] + size[x], );
}
}
return ;
}
虽然都能过，不过树状数组比线段树快了一倍