树剖板子 5Wa 求调
查看原帖
树剖板子 5Wa 求调
141392
lucky叶楼主2021/10/28 16:20
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long
#define l(x) x << 1
#define r(x) x << 1 | 1
using namespace std;
const int N = 2e5 + 5, M = N * 2;
int n, m, root;
int a[N];
int idx;
int e[M], ne[M], h[N], top[N];
void add(int x, int y)
{
	idx ++;
	e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
int father[N], d[N], son[N], id[N], nw[N], cnt;
int sz[N];
struct Node{
	int l, r;
	LL add, sum;
}tr[N << 2];
void dfs(int x, int p, int depth)
{
	d[x] = depth;
	father[x] = p;
	sz[x] = 1;
	son[x] = n + 1;
	for(int i = h[x]; ~i; i = ne[i])
	{
		int j = e[i];
		if(j == p) continue;
		dfs(j, x, depth + 1);
		sz[x] += sz[j];
		if(sz[son[x]] < sz[j]) son[x] = j;
	}
}
void dfs2(int x, int t)
{
	id[x] = ++ cnt, nw[cnt] = a[x], top[x] = t;
	if(!son[x]) return ;
	dfs2(son[x], t);
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i];
		if(j == father[x] || j == son[x]) continue;
		dfs2(j, j);
	}
}
void pushup(int x)
{
	tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
	return ;
}
void pushdown(int x)
{
	if(tr[x].add)
	{
		tr[l(x)].add += tr[x].add;
		tr[l(x)].sum += (tr[l(x)].r - tr[l(x)].l + 1) * tr[x].add;
		tr[r(x)].add += tr[x].add;
		tr[r(x)].sum += (tr[r(x)].r - tr[r(x)].l + 1) * tr[x].add;
		tr[x].add = 0;
	}
}
void build(int x, int l ,int r)
{
	if(l == r)
	{
		tr[x].l = tr[x].r = l;
		tr[x].add = 0;
		tr[x].sum = nw[l];
		return ;
	}
	tr[x].l = l, tr[x].r = r;
	int mid = l + r >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	pushup(x);
	return ;
}
void modify(int x, int l, int r, int k)
{
	if(l <= tr[x].l && tr[x].r <= r)
	{
		tr[x].sum += (tr[x].r - tr[x].l + 1) * k;
		tr[x].add += k;
		return ;
	}
	pushdown(x);
	int mid = tr[x].l + tr[x].r >> 1;
	if(l <= mid) modify(x << 1, l, r, k);
	if(r > mid) modify(x << 1 | 1, l, r, k);
	pushup(x);
}
LL query(int x, int l, int r)
{
	if(l <= tr[x].l && tr[x].r <= r) return tr[x].sum;
	pushdown(x);
	int mid = tr[x].l + tr[x].r >> 1;
	LL ans = 0;
	if(l <= mid) ans += query(x << 1, l, r);
	if(r > mid) ans += query(x << 1 | 1, l, r);
	return ans;
}
void update_path(int u, int v, int k)
{
	while(top[u] != top[v])
	{
		if(d[top[u]] < d[top[v]]) swap(u, v);
		modify(1, id[top[u]], id[u], k);
		u = father[top[u]];
	}
	if(d[u] < d[v]) swap(u, v);
	modify(1, id[v], id[u], k);
}
LL query_path(int u, int v)
{
	LL res = 0;
	while(top[u] != top[v])
	{
		if(d[top[u]] < d[top[v]]) swap(u, v);
		res += query(1, id[top[u]], id[u]);
		u = father[top[u]];
	}
	if(d[u] < d[v]) swap(u, v);
	res += query(1, id[v], id[u]);
	return res;
}
LL query_tree(int x)
{
	return query(1, id[x], id[x] + sz[x] - 1);
}
int main()
{
	memset(h, -1, sizeof(h));
	scanf("%d", &n);
	for(int i = 1;i < n;i ++)
	{
		int o, u;
		scanf("%d%d", &o, &u);
		add(o, u);
		add(u, o);
	}
	root = 0;
	dfs(root, -1, 1);
	dfs2(root, root);
	build(1, 1, cnt);
	scanf("%d", &m);
	while(m --)
	{
		int  t, u, v, k;
		char op[2];
		scanf("%s", op);
		if(op[0] == 'A')
		{
			int u, v, d;
			scanf("%d%d%d", &u, &v, &k);
			update_path(u, v, k);
//			for(int i = 0;i < n;i ++)
//			cout << "i: " <<i << " " << query_tree(0) << endl;
		}
		if(op[0] == 'Q')
		{
			int u;
			scanf("%d", &u);
			printf("%lld\n", query_tree(u));
		}
	}
	//query(1, dfn[x], dfn[x] + sz[x] - 1);
	return 0;
}
2021/10/28 16:20
加载中...