[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1103
[算法]
树链剖分
时间复杂度 : O(NlogN ^ 2)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 250010 typedef long long LL; int n , tot , timer; int head[MAXN] , dfn[MAXN] , top[MAXN] , fa[MAXN] , size[MAXN] , son[MAXN] , depth[MAXN]; struct edge { int to , nxt; } e[MAXN << 1]; struct Segment_Tree { struct Node { int l , r; int sum , tag; } Tree[MAXN << 2]; inline void build(int index , int l , int r) { Tree[index] = (Node){l , r , r - l + 1 , 0}; if (l == 1) --Tree[index].sum; if (l == r) return; int mid = (Tree[index].l + Tree[index].r) >> 1; build(index << 1 , l , mid); build(index << 1 | 1 , mid + 1 , r); } inline void pushdown(int index) { int l = Tree[index].l , r = Tree[index].r; int mid = (l + r) >> 1; if (Tree[index].tag) { Tree[index << 1].sum = Tree[index << 1 | 1].sum = 0; Tree[index << 1].tag = Tree[index << 1 | 1].tag = 1; } } inline void update(int index) { Tree[index].sum = Tree[index << 1].sum + Tree[index << 1 | 1].sum; } inline void modify(int index , int l , int r) { if (l > r) return; if (Tree[index].l == l && Tree[index].r == r) { Tree[index].sum = 0; Tree[index].tag = 1; return; } pushdown(index); int mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) modify(index << 1 , l , r); else if (mid + 1 <= l) modify(index << 1 | 1 , l , r); else { modify(index << 1 , l , mid); modify(index << 1 | 1 , mid + 1 , r); } update(index); } inline int query(int index , int l , int r) { if (l > r) return 0; if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum; pushdown(index); int mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) return query(index << 1 , l , r); else if (mid + 1 <= l) return query(index << 1 | 1 , l , r); else return query(index << 1 , l , mid) + query(index << 1 | 1 , mid + 1 , r); } } SGT; template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); } template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v) { ++tot; e[tot] = (edge){v , head[u]}; head[u] = tot; } inline void dfs1(int u) { size[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == fa[u]) continue; fa[v] = u; depth[v] = depth[u] + 1; dfs1(v); size[u] += size[v]; if (size[v] > size[son[u]]) son[u] = v; } } inline void dfs2(int u , int tp) { dfn[u] = ++timer; top[u] = tp; if (son[u]) dfs2(son[u] , tp); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == fa[u] || v == son[u]) continue; dfs2(v , v); } } inline void modify(int u , int v) { int tu = top[u] , tv = top[v]; while (tu != tv) { if (depth[tu] > depth[tv]) { swap(u , v); swap(tu , tv); } SGT.modify(1 , dfn[tv] , dfn[v]); v = fa[tv]; tv = top[v]; } if (depth[u] > depth[v]) swap(u , v); SGT.modify(1 , dfn[u] + 1 , dfn[v]); } inline int query(int u) { int tu = top[u] , ret = 0; while (tu != 1) { ret += SGT.query(1 , dfn[tu] , dfn[u]); u = fa[tu]; tu = top[u]; } ret += SGT.query(1 , 1 , dfn[u]); return ret; } int main() { scanf("%d" , &n); for (int i = 1; i < n; i++) { int u , v; scanf("%d%d" , &u , &v); addedge(u , v); addedge(v , u); } dfs1(1); dfs2(1 , 1); SGT.build(1 , 1 , n); int m; scanf("%d" , &m); for (int i = 1; i <= n + m - 1; i++) { char op[5]; scanf("%s" , &op); if (op[0] == 'A') { int u , v; scanf("%d%d" , &u , &v); modify(u , v); } else { int u; scanf("%d" , &u); printf("%d " , query(u)); } } return 0; }