題目大意：給出一棵樹，有n個問題，詢問在[l,r]區間內的每個節點i與z的最近公共祖先的深度之和。
思路：不會，然後看了題解，之後發現自己智商嚴重不足。
看到數據范圍就知道一定要離線處理，就這個離線處理我估計以我的智商不看題解是肯定想不出來的。。
考慮這樣的一種暴力，我們把 z 到根上的點全部打標記，對於 l 到 r 之間的點，向上搜索到第一個有標記的點求出它的深度統計答案。觀察到，深度其實就是上面有幾個已標記了的點（包括自身）。所以，我們不妨把 z 到根的路徑上的點全部 +1，對於 l 到 r 之間的點詢問他們到根路徑上的點權和。仔細觀察上面的暴力不難發現，實際上這個操作具有疊加性，且可逆。也就是說我們可以對於 l 到 r 之間的點 i，將 i 到根的路徑上的點全部 +1, 轉而詢問 z 到根的路徑上的點（包括自身）的權值和就是這個詢問的答案。把詢問差分下，也就是用
[1, r] ? [1, l ? 1] 來計算答案，那麼現在我們就有一個明顯的解法。從 0 到 n ? 1 依次插入點 i，即將 i 到根的路徑上的點全部+1。離線詢問答案即可。我們現在需要一個數據結構來維護路徑加和路徑求和，顯然樹鏈剖分或LCT 均可以完成這個任務。樹鏈剖分的復雜度為 O((n + q)· log n · log n)，LCT的復雜度為 O((n + q)· log n)，均可以完成任務。至此，題目已經被我們完美解決。
神題啊。。。
CODE：
#include#include #include #include #define MAX 100010 #define INF 0x3f3f3f3f #define LEFT (pos << 1) #define RIGHT (pos << 1|1) #define CNT (r - l + 1) #define MO 201314 using namespace std; struct _Ask{ bool is_l; int x,z; int id; _Ask(bool _,int __,int ___,int ____):is_l(_),x(__),z(___),id(____) {} _Ask() {} bool operator <(const _Ask &a)const { if(x == a.x) return is_l; return x < a.x; } }ask[MAX]; struct SegTree{ long long sum; int c; }tree[MAX << 2]; int points,asks; int head[MAX],total; int next[MAX],aim[MAX]; int deep[MAX],father[MAX],son[MAX],size[MAX]; int pos[MAX],top[MAX],cnt; long long ans[MAX]; inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void PreDFS(int x) { deep[x] = deep[father[x]] + 1; size[x] = 1; int max_size = 0,p = 0; for(int i = head[x]; i; i = next[i]) { PreDFS(aim[i]); size[x] += size[aim[i]]; if(max_size < size[aim[i]]) max_size = size[aim[i]],p = aim[i]; } son[x] = p; } void DFS(int x,int _top) { pos[x] = ++cnt; top[x] = _top; if(son[x]) DFS(son[x],_top); for(int i = head[x]; i; i = next[i]) { if(aim[i] == son[x]) continue; DFS(aim[i],aim[i]); } } inline void PushDown(int pos,int cnt) { if(tree[pos].c) { tree[LEFT].sum += tree[pos].c * (cnt - (cnt >> 1)); tree[RIGHT].sum += tree[pos].c * (cnt >> 1); tree[LEFT].c += tree[pos].c; tree[RIGHT].c += tree[pos].c; tree[pos].c = 0; } } void Modify(int l,int r,int x,int y,int pos) { if(l == x && r == y) { tree[pos].sum += CNT; ++tree[pos].c; return ; } PushDown(pos,CNT); int mid = (l + r) >> 1; if(y <= mid) Modify(l,mid,x,y,LEFT); else if(x > mid) Modify(mid + 1,r,x,y,RIGHT); else { Modify(l,mid,x,mid,LEFT); Modify(mid + 1,r,mid + 1,y,RIGHT); } tree[pos].sum = tree[LEFT].sum + tree[RIGHT].sum; } inline void Modify(int x) { while(x) { Modify(1,cnt,pos[top[x]],pos[x],1); x = father[top[x]]; } } long long Ask(int l,int r,int x,int y,int pos) { if(l == x && y == r) return tree[pos].sum; PushDown(pos,CNT); int mid = (l + r) >> 1; if(y <= mid) return Ask(l,mid,x,y,LEFT); if(x > mid) return Ask(mid + 1,r,x,y,RIGHT); long long left = Ask(l,mid,x,mid,LEFT); long long right = Ask(mid + 1,r,mid + 1,y,RIGHT); return left + right; } inline long long Ask(int x) { long long re = 0; while(x) { re += Ask(1,cnt,pos[top[x]],pos[x],1); x = father[top[x]]; } return re; } int main() { cin >> points >> asks; for(int x,i = 2; i <= points; ++i) { scanf("%d",&x),++x; Add(x,i); father[i] = x; } PreDFS(1); DFS(1,1); for(int num = 0,x,y,z,i = 1; i <= asks; ++i) { scanf("%d%d%d",&x,&y,&z); ++x,++y,++z; ask[++num] = _Ask(true,x - 1,z,i); ask[++num] = _Ask(false,y,z,i); } sort(ask + 1,ask + (asks << 1) + 1); int j = 1; for(int i = 0; i <= points; ++i) { Modify(i); for(; ask[j].x == i; ++j) if(ask[j].is_l) ans[ask[j].id] = Ask(ask[j].z); else ans[ask[j].id] = (Ask(ask[j].z) - ans[ask[j].id]) % MO; } for(int i = 1; i <= asks; ++i) printf("%d\n",(int)ans[i]); return 0; }
