CF916E Jamie and Tree

题意翻译
有一棵n个节点的有根树，标号为1-n，你需要维护以下三种操作

1.给定一个点v，将整颗树的根变为v

2.给定两个点u, v，将lca(u, v)所在的子树都加上x

3.给定一个点v，你需要回答以v所在的子树的权值和

Translated by mangoyang

错误日志：第一次 (debug) 是 (jump) 数组第二维开小了；交了一次错了，第二次没有特判修改/查询节点等于根的情况；第三次 (RE) 又是数组开销了。。。空间那么大我倒是把数组卡大点啊啊啊

Solution

树链剖分，要求换根修改和查询

(lca(u,v)) 等于 (lca(u, v) ,lca(u, root) ,lca(v, root)) 里深度最大的点
修改和查询：分三种情况考虑：

操作节点为根节点：直接操作于整棵树
根节点在操作节点子树之外：直接操作即可
根节点位于操作节点子树内：利用容斥（最好画图看看）。设点 (son) 为从根节点到操作节点路径上的倒数第二个点，先整棵树更新，再将 (son) 的子树减去更新值即可
（又或者常数较大的先更新整棵树，反过来减去操作节点的子树，再更新操作节点这一个点）

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
LL RD(){
    LL out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const LL maxn = 200019,INF = 1e9 + 19;
LL head[maxn],nume = 1;
struct Node{
    LL v,dis,nxt;
    }E[maxn << 2];
void add(LL u,LL v,LL dis){
    E[++nume].nxt = head[u];
    E[nume].v = v;
    E[nume].dis = dis;
    head[u] = nume;
    }
LL num, na;
LL dep[maxn], size[maxn], fa[maxn], wson[maxn], top[maxn], pos[maxn], ori[maxn], cnt;
LL v[maxn];
void dfs1(LL id, LL F){
	size[id] = 1;
	for(LL i = head[id];i;i = E[i].nxt){
		LL v = E[i].v;
		if(v == F)continue;
		dep[v] = dep[id] + 1;
		fa[v] = id;
		dfs1(v, id);
		size[id] += size[v];
		if(size[v] > size[wson[id]])wson[id] = v;
		}
	}
void dfs2(LL id, LL TP){
	pos[id] = ++cnt;
	ori[cnt] = id;
	top[id] = TP;
	if(!wson[id])return ;
	dfs2(wson[id], TP);
	for(LL i = head[id];i;i = E[i].nxt){
		LL v = E[i].v;
		if(v == fa[id] || v == wson[id])continue;
		dfs2(v, v);
		}
	}
#define lid (id << 1)
#define rid (id << 1) | 1
struct seg_tree{
	LL l, r;
	LL lazy, sum;
	}tree[maxn << 2];
void pushup(LL id){tree[id].sum = tree[lid].sum + tree[rid].sum;}
void pushdown(LL id){
	if(tree[id].lazy){
		LL val = tree[id].lazy;
		tree[lid].lazy += val;
		tree[rid].lazy += val;
		tree[lid].sum += (tree[lid].r - tree[lid].l + 1) * val;
		tree[rid].sum += (tree[rid].r - tree[rid].l + 1) * val;
		tree[id].lazy = 0;
		}
	}
void build(LL id, LL l, LL r){
	tree[id].l = l, tree[id].r = r;
	if(l == r){
		tree[id].sum = v[ori[l]];
		return ;
		}
	LL mid = (l + r) >> 1;
	build(lid, l, mid), build(rid, mid + 1, r);
	pushup(id);
	}
void update(LL id, LL val, LL l, LL r){
	pushdown(id);
	if(tree[id].l == l && tree[id].r == r){
		tree[id].sum += (tree[id].r - tree[id].l + 1) * val;
		tree[id].lazy += val;
		return ;
		}
	LL mid = (tree[id].l + tree[id].r) >> 1;
	if(mid < l)update(rid, val, l, r);
	else if(mid >= r)update(lid, val, l, r);
	else update(lid, val, l, mid), update(rid, val, mid + 1, r);
	pushup(id);
	}
LL query(LL id, LL l ,LL r){
	pushdown(id);
	if(tree[id].l == l && tree[id].r == r){
		return tree[id].sum;
		}
	LL mid = (tree[id].l + tree[id].r) >> 1;
	if(mid < l)return query(rid, l, r);
	else if(mid >= r)return query(lid, l, r);
	else return query(lid, l, mid) + query(rid, mid + 1, r);
	}
LL root = 1, jump[maxn][25];
void get_jump(){
	for(LL i = 1;i <= num;i++)jump[i][0] = fa[i];
	for(LL i = 1;i <= 19;i++){
		for(LL j = 1;j <= num;j++){
			jump[j][i] = jump[jump[j][i - 1]][i - 1];
			}
		}
	}
LL LCA(LL x, LL y){
	if(dep[x] < dep[y])swap(x, y);
	for(LL i = 19;i >= 0;i--)if(dep[jump[x][i]] >= dep[y])x = jump[x][i];
	if(x == y)return x;
	for(LL i = 19;i >= 0;i--)if(jump[x][i] != jump[y][i])x = jump[x][i], y = jump[y][i];
	return jump[x][0];
	}
LL real_LCA(LL x, LL y){
	LL lca1 = LCA(x, y), lca2 = LCA(x, root), lca3 = LCA(y, root);
	LL lca = dep[lca1] > dep[lca2] ? lca1 : lca2;
	return dep[lca] > dep[lca3] ? lca : lca3;
	}
LL son_LCA(LL x, LL y = root){
	if(dep[x] >= dep[y])return -1;
	for(LL i = 19;i >= 0;i--)if(dep[jump[y][i]] >= dep[x] + 1)y = jump[y][i];
	if(fa[y] == x)return y;
	return -1;
	}
void change_root(){root = RD();}
void uprange(){
	LL x = RD(), y = RD(), val = RD();
	LL lca = real_LCA(x, y);
	if(lca == root){update(1, val, pos[1], pos[1] + size[1] - 1);return ;}
	LL son = son_LCA(lca);
	if(son == -1){update(1, val, pos[lca], pos[lca] + size[lca] - 1);return ;}
	update(1, val, pos[1], pos[1] + size[1] - 1);
	update(1,-val, pos[son], pos[son] + size[son] - 1);
	}
void get_sum(){
	LL x = RD();
	if(x == root){printf("%lld
", query(1, pos[1], pos[1] + size[1] - 1));return ;}
	LL son = son_LCA(x);
	if(son == -1){printf("%lld
", query(1, pos[x], pos[x] + size[x] - 1));return ;}
	printf("%lld
", query(1, pos[1], pos[1] + size[1] - 1) - query(1, pos[son], pos[son] + size[son] - 1));
	}
int main(){
	num = RD();na = RD();
	for(LL i = 1;i <= num;i++)v[i] = RD();
	for(LL i = 1;i <= num - 1;i++){
		LL u = RD(), v = RD();
		add(u, v, 1), add(v, u, 1);
		}
	dep[1] = 1;
	dfs1(1, -1), dfs2(1, 1);
	build(1, 1, num);
	get_jump();
	for(LL i = 1;i <= na;i++){
		LL cmd = RD();
		if(cmd == 1)change_root();
		else if(cmd == 2)uprange();
		else get_sum();
		}
	return 0;
	}