[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=1103

[算法]

树链剖分

时间复杂度 : O(NlogN ^ 2)

[代码]

#include
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 << ];

struct Segment_Tree
{
struct Node
{
int l , r;
int sum , tag;
} Tree[MAXN << ]; inline void build(int index , int l , int r) { Tree[index] = (Node){l , r , r - l + , }; if (l == ) --Tree[index].sum; if (l == r) return; int mid = (Tree[index].l + Tree[index].r) >> ;
build(index << , l , mid); build(index << | , mid + , r); } inline void pushdown(int index) { int l = Tree[index].l , r = Tree[index].r; int mid = (l + r) >> ;
if (Tree[index].tag)
{
Tree[index << ].sum = Tree[index << | ].sum = ; Tree[index << ].tag = Tree[index << | ].tag = ; } } inline void update(int index) { Tree[index].sum = Tree[index << ].sum + Tree[index << | ].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 = ;
Tree[index].tag = ;
return;
}
pushdown(index);
int mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) modify(index << , l , r); else if (mid + <= l) modify(index << | , l , r); else { modify(index << , l , mid); modify(index << | , mid + , r); } update(index); } inline int query(int index , int l , int r) { if (l > r) return ;
if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum;
pushdown(index);
int mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) return query(index << , l , r);
else if (mid + <= l) return query(index << | , l , r);
else return query(index << , l , mid) + query(index << | , mid + , r);
}
} SGT;

template inline void chkmax(T &x , T y) { x = max(x , y); }
template inline void chkmin(T &x , T y) { x = min(x , y); }
template inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - ''; 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] = ; 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] + ; 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( , dfn[tv] , dfn[v]);
v = fa[tv]; tv = top[v];
}
if (depth[u] > depth[v]) swap(u , v);
SGT.modify( , dfn[u] + , dfn[v]);
}
inline int query(int u)
{
int tu = top[u] , ret = ;
while (tu != )
{
ret += SGT.query( , dfn[tu] , dfn[u]);
u = fa[tu]; tu = top[u];
}
ret += SGT.query( , , dfn[u]);
return ret;
}

int main()
{

scanf("%d" , &n);  
for (int i = ; i < n; i++)  
{  
    int u , v;  
    scanf("%d%d" , &u , &v);  
    addedge(u , v);  
    addedge(v , u);  
}  
dfs1();  
dfs2( , );  
SGT.build( ,  , n);  
int m;  
scanf("%d" , &m);  
for (int i = ; i <= n + m - ; i++)  
{  
    char op\[\];  
    scanf("%s" , &op);  
    if (op\[\] == 'A')  
    {  
        int u , v;  
        scanf("%d%d" , &u , &v);  
        modify(u , v);  
    } else  
    {  
        int u;  
        scanf("%d" , &u);  
        printf("%d\\n" , query(u));  
    }  
}

return ;  

}