【luogu P3178 [HAOI2015]树上操作】题解

题目链接：https://www.luogu.org/problemnew/show/P3178

模板题菜
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lson left, mid, rt<<1

#define rson mid + 1, right, rt<<1|1

#define ll long long

using namespace std;

const int maxn = 200000 + 10;

ll n, m, root, mod;

ll node[maxn], num;

ll fa[maxn], dep[maxn], size[maxn], son[maxn], top[maxn], seg[maxn], rev[maxn];

ll res;

struct edge{

	ll from, to, next;

}e[maxn<<2];

ll head[maxn], cnt;

//-------------------------------------------------------

ll tree[maxn<<2], lazy[maxn<<2];

void PushUP(ll rt)

{

	tree[rt] = (tree[rt<<1] + tree[rt<<1|1]);

}

void build(ll left, ll right, ll rt)

{

	if(left == right)

	{

		tree[rt] = rev[left];

		tree[rt] = tree[rt];

		return;

	}

	ll mid = (left + right) >> 1;

	build(lson);

	build(rson);

	PushUP(rt);

}

void PushDOWN(ll left, ll right, ll rt, ll mid)

{

	lazy[rt<<1] += lazy[rt];

	lazy[rt<<1|1] += lazy[rt];

	tree[rt<<1] += (mid - left + 1)*lazy[rt];

	tree[rt<<1|1] += (right - mid)*lazy[rt];

	lazy[rt] = 0;

}

ll query(ll l, ll r, ll left, ll right, ll rt)

{

	ll res = 0;

	if(l <= left && r >= right)

	{

		return tree[rt];

	}

	ll mid = (left + right)>>1;

	if(lazy[rt]) PushDOWN(left, right, rt, mid);

	if(l <= mid) res += query(l, r, lson);

	if(r > mid) res += query(l, r, rson);

	return res;

}

void update(ll l, ll r, ll add, ll left, ll right, ll rt)

{

	if(l <= left && r >= right)

	{

		lazy[rt] += add;

		tree[rt] += (right - left + 1)*add;

		return;

	}

	ll mid = (left + right)>>1;

	PushDOWN(left, right, rt, mid);

	if(l <= mid) update(l, r, add, lson);

	if(r > mid) update(l, r, add, rson);

	PushUP(rt);

}

//------------------------------------------------

void add(ll u, ll v)

{

	e[++cnt].from = u;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

void dfs1(ll u, ll f, ll d)

{

	ll maxson = -1;

	size[u] = 1;

	fa[u] = f;

	dep[u] = d;

	for(ll i = head[u]; i != -1; i = e[i].next)

	{

		ll v = e[i].to;

		if(v != f)

		{

			dfs1(v, u, d + 1);

			size[u] += size[v];

			if(size[v] > maxson) son[u] = v, maxson = size[v];

		}

	}

}

void dfs2(ll u, ll t)

{

	seg[u] = ++num;

	rev[num] = node[u];

	top[u] = t;

	if(!son[u]) return;

	dfs2(son[u], t);

	for(ll i = head[u]; i != -1; i = e[i].next)

	{

		ll v = e[i].to;

		if(fa[u] == v || son[u] == v) continue;

		dfs2(v, v);

	}

}

ll qRange(ll x, ll y)

{

	ll ans = 0;

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x, y);

		res = 0;

		res = query(seg[top[x]], seg[x], 1, n, 1);

		ans = ans + res;

		x = fa[top[x]];

	}

	if(dep[x] > dep[y]) swap(x, y);

	res = 0;

	res = query(seg[x], seg[y], 1, n, 1);

	ans = ans + res;

	return ans;

}

void updRange(ll x, ll y, ll k)

{

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]]) swap(x, y);

		update(seg[top[x]], seg[x], k, 1, n, 1);

		x = fa[top[x]];

	}

	if(dep[x] > dep[y]) swap(x, y);

	update(seg[x], seg[y], k, 1, n, 1);

}

ll qSon(ll x)

{

	res = 0;

	res = query(seg[x], seg[x]+size[x]-1, 1, n, 1);

	return res;

}

ll updSon(ll x, ll k)

{

	update(seg[x], seg[x]+size[x]-1, k, 1, n, 1);

}

int main()

{

	memset(head, -1, sizeof(head));

	scanf("%lld%lld",&n,&m);

	root = 1;

	for(ll i = 1; i <= n; i++)

	scanf("%lld",&node[i]);

	for(ll i = 1; i < n; i++)

	{

		ll u, v;

		scanf("%lld%lld",&u,&v);

		add(u, v), add(v, u);

	}

	dfs1(root, 0, 1);

	dfs2(root, root);

	build(1,n,1);

	for(ll i = 1; i <= m; i++)

	{

		ll opt, x, y, z;

		scanf("%lld",&opt);

		if(opt == 1)

		{

			scanf("%lld%lld%",&x,&y);

			updRange(x, x, y);

		}

		if(opt == 2)

		{

			scanf("%lld%lld",&x,&y);

			updSon(x, y);

		}

		if(opt == 3)

		{

			scanf("%lld",&x);

			printf("%lld\n",qRange(x, 1));

		}

	}

	return 0;

}
巴特西

【luogu P3178 [HAOI2015]树上操作】题解

最新文章

热门文章

巴特西

【luogu P3178 [HAOI2015]树上操作】 题解

最新文章

热门文章

【luogu P3178 [HAOI2015]树上操作】题解
