https://www.luogu.org/problemnew/show/T28848#sub

#include <iostream>
#include <cstdio> using namespace std;
const int N = 1e5 + ; int top[N], fa[N], deep[N], size[N], son[N], tree[N], bef[N];
int head[N], W[N << ], F[N << ], Size[N << ];
int n, Ty, tim, now = ;
struct Node{int v, nxt;} G[N << ];
int Answer; #define gc getchar() inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} inline void Add(int u, int v) {G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;} void Dfs_1(int u, int dep, int f_) {
deep[u] = dep; fa[u] = f_;
size[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != f_) {
Dfs_1(v, dep + , u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
} void Dfs_2(int u, int tp) {
top[u] = tp;
tree[u] = ++ tim;
if(!son[u]) return ;
Dfs_2(son[u], tp);
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != fa[u] && v != son[u]) Dfs_2(v, v);
}
} #define lson jd << 1
#define rson jd << 1 | 1 void Build_tree(int l, int r, int jd) {
Size[jd] = r - l + ;
if(l == r) {
W[jd] = ;
return ;
}
int mid = (l + r) >> ;
Build_tree(l, mid, lson);
Build_tree(mid + , r, rson);
W[jd] = W[lson] + W[rson];
} void Down(int jd) {
int f = F[jd];
W[lson] += Size[lson] * f; W[rson] += Size[rson] * f;
F[lson] += f; F[rson] += f;
F[jd] = ;
} void Sec_G(int l, int r, int jd, int x, int y, int yj) {
if(x <= l && r <= y) {W[jd] += (r - l + ) * yj; F[jd] += yj; return ;}
if(F[jd]) Down(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_G(l, mid, lson, x, y, yj);
if(y > mid) Sec_G(mid + , r, rson, x, y, yj);
W[jd] = W[lson] + W[rson];
} inline void Sec_G_imp(int x, int y) {
int tp1 = top[x], tp2 = top[y];
while(tp1 != tp2) {
if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
Sec_G(, n, , tree[tp1], tree[x], -);
x = fa[tp1];
tp1 = top[x];
}
if(x == y) return ;
if(deep[x] < deep[y]) swap(x, y);
Sec_G(, n, , tree[y] + , tree[x], -);
} void Sec_A(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) {
Answer += W[jd]; return ;
}
if(F[jd]) Down(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_A(l, mid, lson, x, y);
if(y > mid) Sec_A(mid + , r, rson, x, y);
} inline int Sec_A_imp(int x) {
int tp1 = top[x], ret = ;
while(tp1 != ) {
Answer = ;
Sec_A(, n, , tree[tp1], tree[x]);
ret += Answer;
x = fa[tp1];
tp1 = top[x];
}
if(x == ) return ret;
Answer = ;
Sec_A(, n, , tree[] + , tree[x]);
ret += Answer;
return ret;
} int main() {
n = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i < n; i ++) {
int u = read(), v = read();
Add(u, v); Add(v, u);
}
Dfs_1(, , );
Dfs_2(, );
Build_tree(, n, );
Ty = read();
Ty = Ty + n - ;
while(Ty --) {
string opt;
cin >> opt;
if(opt[] == 'A') {
int x = read(), y = read();
Sec_G_imp(x, y);
}
else {
int x = read();
cout << Sec_A_imp(x) << "\n";
}
} return ;
}
/*
5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3
*/

最新文章

  1. WordPress建站 新手入门
  2. C# 自定义文件图标 双击启动 (修改注册表)
  3. [转]PO和VO、关于延迟加载(lazy)和强制加载(Hibernate.initialize(Object proxy) )
  4. 关于JAVA System常见类的一些总结
  5. OC6-网址分割
  6. Visual Studio.NET、asp.net和C#间的关系是怎样的?
  7. ASP.Net_入门准备
  8. 深入 char * ,char ** ,char a[ ] ,char *a[] 内核
  9. c# winform panel 流式布局 panel块可自动排列
  10. 使用ThinkPHP的扩展功能
  11. css样式--表格
  12. python基础学习(一)
  13. iOS开发支付集成之微信支付
  14. nodejs adm-zip 解压文件 中文文件名乱码 问题解决
  15. [Swift]LeetCode1021. 删除最外层的括号 | Remove Outermost Parentheses
  16. 虽然不抱希望但也愿.Net和Java之争暂得平息
  17. 数组去重的4种方法(Which one is the fastest???嘻嘻嘻....)
  18. 20165323 实验二 Java面向对象程序设计
  19. 我的Java之旅 第六课 JAVA WEB 请求与响应
  20. mysql操作命令梳理(5)-执行sql语句查询即mysql状态说明

热门文章

  1. S02_CH08_ ZYNQ 定时器中断实验
  2. 【树上异或和计数】czr 太弱啦
  3. Asp.net core 学习笔记 QR code and Barcode
  4. Spring Boot 获取Bean对象实体
  5. 在javascript对象内搜索,貌似是一个新鲜的话题。
  6. MySQL间隙锁问题
  7. [react] - 循环请求 redux-saga
  8. pandas库的一些操作
  9. web开发:Bootstrap应用及内存管理
  10. vscode 右键打开