傳送門：嘟嘟嘟
?
第一反應是樹鏈剖分，但是太長懶得寫，然后就想出了一個很不錯的做法。
想一下，如果我們改一條邊，那么影響的只有他的子樹，只要先搞一個dfs序，為什么搞出這個呢？因為有一個性質：一個節點的子樹在dfs序上是連續的，所以這道題就變成了一個單點查詢，區間修改的線段樹（樹狀數組）板子題。
?
然后我不到40分鐘寫完了，非說有的點TLE，debug了一個多點……現在想想，一般遇到這種情況，一定不是什么正經問題。然而當時的我并不這么想，以為線段樹太慢了，改成差分+樹狀數組，各種優化，雖然在luogu卡了過去，然而內網卻GG。
終于放棄，到網上找標程，發現寫的幾乎一模一樣，就一行行比對……然后發現我為了省事兒讀字母用了cin，按標稱改成了scanf……結果最慢的點直接從900多ms變成了200多ms……然后內網秒過了……老子在此立flag：我，mrclr，如果再用cin，我就女裝！
?
心路歷程講完了，發下代碼吧
先是線段樹的
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cmath> 6 #include<stack> 7 #include<queue> 8 #include<vector> 9 #include<cstdlib> 10 #include<cctype> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 3e5 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) 26 { 27 ans = ans * 10 + ch - '0'; ch = getchar(); 28 } 29 if(last == '-') ans = -ans; 30 return ans; 31 } 32 inline void write(ll x) 33 { 34 if(x < 0) putchar('-'), x = -x; 35 if(x >= 10) write(x / 10); 36 putchar(x % 10 + '0'); 37 } 38 39 int n; 40 vector<int> v[maxn]; 41 42 int dis[maxn], dfsx[maxn], size[maxn], pos[maxn], cnt = 0; 43 void dfs(const int& now) 44 { 45 dfsx[now] = ++cnt; pos[cnt] = now; 46 size[now] = 1; 47 for(int i = 0; i < (int)v[now].size(); ++i) 48 { 49 dis[v[now][i]] = dis[now] + 1; 50 dfs(v[now][i]); 51 size[now] += size[v[now][i]]; 52 } 53 return; 54 } 55 56 int l[maxn << 2], r[maxn << 2], dis2[maxn << 2], lazy[maxn << 2]; 57 void build(const int& L, const int& R, const int& now) 58 { 59 l[now] = L; r[now] = R; 60 if(L == R) {dis2[now] = dis[pos[L]]; return;} 61 int mid = (L + R) >> 1; 62 build(L, mid, now << 1); 63 build(mid + 1, R, now << 1 | 1); 64 dis2[now] = dis2[now << 1] + dis2[now << 1 | 1]; 65 } 66 void pushdown(const int& now) 67 { 68 if(lazy[now]) 69 { 70 lazy[now << 1] += lazy[now]; 71 lazy[now << 1 | 1] += lazy[now]; 72 dis2[now << 1] -= lazy[now]; 73 dis2[now << 1 | 1] -= lazy[now]; 74 lazy[now] = 0; 75 } 76 } 77 void update(const int& L, const int& R, const int& now) 78 { 79 if(!dis2[now]) return; 80 if(l[now] == L && r[now] == R) 81 { 82 dis2[now]--; lazy[now]++; 83 return; 84 } 85 pushdown(now); 86 int mid = (l[now] + r[now]) >> 1; 87 if(R <= mid) update(L, R, now << 1); 88 else if(L > mid) update(L, R, now << 1 | 1); 89 else {update(L, mid, now << 1); update(mid + 1, R, now << 1 | 1);} 90 } 91 int query(const int& id, const int& now) 92 { 93 if(!dis2[now]) return 0; 94 if(l[now] == r[now]) return dis2[now]; 95 pushdown(now); 96 int mid = (l[now] + r[now]) >> 1; 97 if(id <= mid) return query(id, now << 1); 98 else return query(id, now << 1 | 1); 99 } 100 101 int main() 102 { 103 n = read(); 104 for(int i = 1; i < n; ++i) 105 { 106 int x = read(), y = read(); 107 if(y < x) swap(x, y); 108 v[x].push_back(y); 109 } 110 dfs(1); 111 build(1, cnt, 1); 112 int m = read(); 113 char ch[5]; 114 for(int i = 1; i < n + m; ++i) 115 { 116 scanf("%s", ch); 117 if(ch[0] == 'W') 118 { 119 int x = read(); 120 write(query(dfsx[x], 1)); enter; 121 } 122 else 123 { 124 int x = read(), y = read(); 125 if(y > x) swap(x, y); 126 update(dfsx[x], dfsx[x] + size[x] - 1, 1); 127 } 128 } 129 return 0; 130 }
然后又寫了個差分+樹狀數組
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cmath> 6 #include<stack> 7 #include<queue> 8 #include<vector> 9 #include<cstdlib> 10 #include<cctype> 11 using namespace std; 12 #define enter printf("\n") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 3e5 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) 26 { 27 ans = ans * 10 + ch - '0'; ch = getchar(); 28 } 29 if(last == '-') ans = -ans; 30 return ans; 31 } 32 inline void write(ll x) 33 { 34 if(x < 0) putchar('-'), x = -x; 35 if(x >= 10) write(x / 10); 36 putchar(x % 10 + '0'); 37 } 38 39 int n; 40 vector<int> v[maxn]; 41 42 int dis[maxn], dfsx[maxn], size[maxn], pos[maxn], cnt = 0; 43 void dfs(const int& now) 44 { 45 dfsx[now] = ++cnt; pos[cnt] = now; 46 size[now] = 1; 47 if(!v[now].size()) return; 48 for(int i = 0; i < (int)v[now].size(); ++i) 49 { 50 dis[v[now][i]] = dis[now] + 1; 51 dfs(v[now][i]); 52 size[now] += size[v[now][i]]; 53 } 54 } 55 56 int cf[maxn], c[maxn]; 57 inline int lowbit(int x) 58 { 59 return x & -x; 60 } 61 void add(int pos, int x) 62 { 63 while(pos <= cnt) 64 { 65 c[pos] += x; 66 pos += lowbit(pos); 67 } 68 } 69 int sum(int pos) 70 { 71 int ret = 0; 72 while(pos) 73 { 74 ret += c[pos]; 75 pos -= lowbit(pos); 76 } 77 return ret; 78 } 79 80 81 int main() 82 { 83 n = read(); 84 for(int i = 1; i < n; ++i) 85 { 86 int x = read(), y = read(); 87 if(y < x) swap(x, y); 88 v[x].push_back(y); 89 } 90 dfs(1); 91 for(int i = 1; i <= cnt; ++i) cf[i] = dis[pos[i]] - dis[pos[i - 1]]; 92 for(int i = 1; i <= cnt; ++i) add(i, cf[i]); 93 int m = read(); 94 char ch[5]; 95 for(int i = 1; i < n + m; ++i) 96 { 97 scanf("%s", ch); 98 if(ch[0] == 'W') 99 { 100 int x = read(); 101 write(sum(dfsx[x])); enter; 102 } 103 else 104 { 105 int x = read(), y = read(); 106 if(y > x) swap(x, y); 107 add(dfsx[x], -1); add(dfsx[x] + size[x], 1); 108 } 109 } 110 return 0; 111 }
雖然都能過，不過樹狀數組比線段樹快了一倍
