目录

• 题目描述
• 思路
• 代码

题目描述

一棵树，有n个节点，根节点为1，每个点有一个权值
有Q个操作，分三种
1.把节点x的权值改为k
2.询问树上x到y路径上的节点的最大权值
3.询问树上x到y路径上的节点的权值和
（都包括x,y本身）

思路

树链剖分模板
ps:
线段树维护最大值取max事是要写准啊
字符串读入用字符数组，否则容易被一些OJ卡T
这俩东西卡我三个小时

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;

struct wh_
{
	ll w, h;
}wh[500250];

ll Fa[500250], h[500250], siz[500250], Z[500250], uid[500250];
ll A[500250], dep[500250], son[500250], top[500250];
ll Tree[5000250], Tremax[5000250];
ll n, Q, t, num;

ll read()
{
	ll x = 0, r = 1; char c = getchar();
	while(c < '0' || c > '9'){if(c == '-')r = -1;c = getchar();}
	while('0' <= c && c <= '9')x = x * 10 + c - 48, c = getchar();
	return x * r;
}

void write(ll k)
{if(k > 9)write(k / 10); putchar(k % 10 + '0');}

void hw(ll x, ll y)
{wh[++t] = (wh_){y, h[x]}; h[x] = t;}

void build(ll now, ll l, ll r)
{
    if(l == r)
	{
		Tree[now] = A[l];
		Tremax[now] = Tree[now];
        return;
    }
    build(now << 1, l, (l + r) >> 1);
    build(now << 1 | 1, ((l + r) >> 1) + 1, r);
    Tree[now] = Tree[now << 1] + Tree[now << 1 | 1];
    Tremax[now] = max(Tremax[now << 1], Tremax[now << 1 | 1]);
}

void Add(ll now, ll l, ll r, ll x, ll y, ll k)
{
	if(x <= l && r <= y)
	{
		Tree[now] = k;
		Tremax[now] = Tree[now];
		return;
	}
	ll mid = (l + r) >> 1;
	if(x <= mid)Add(now << 1, l, mid, x, y, k);
	if(mid + 1 <= y)Add(now << 1 | 1, mid + 1, r, x, y, k);
	Tree[now] = Tree[now << 1] + Tree[now << 1 | 1];
	Tremax[now] = max(Tremax[now << 1], Tremax[now << 1 | 1]);
}

ll Summ(ll now, ll l, ll r, ll x, ll y)
{
	if(x <= l && r <= y)return Tree[now];
	ll ans = 0, mid = (l + r) >> 1;
	if(x <= mid) ans += Summ(now << 1, l, mid, x, y);
	if(mid + 1 <= y) ans += Summ(now << 1 | 1, mid + 1, r, x, y);
	return ans;
}

ll MaxFindd(ll now, ll l, ll r, ll x, ll y)
{
	if(x <= l && r <= y)return Tremax[now];
	ll ans = -1e17, mid = (l + r) >> 1;
	if(x <= mid) ans = max(ans, MaxFindd(now << 1, l, mid, x, y));
	if(mid + 1 <= y) ans = max(ans, MaxFindd(now << 1 | 1, mid + 1, r, x, y));
	return ans;
}

void DFS1(ll now, ll last)
{
	dep[now] = dep[last] + 1;
	ll maxx = -1e17, maxn = 0;
	Fa[now] = last, siz[now] = 1;
	for(ll i = h[now]; i; i = wh[i].h)
	{
		if(wh[i].w == last)continue;	
		DFS1(wh[i].w, now);
		siz[now] = siz[now] + siz[wh[i].w];
		if(maxx < siz[wh[i].w])maxx = siz[wh[i].w], maxn = wh[i].w;
	}
	son[now] = maxn;
	return;
}

void DFS2(ll now, ll tp)
{
	uid[now] = ++num;
	A[num] = Z[now];
	top[now] = tp;
	if(!son[now])return;
	DFS2(son[now], tp);
	for(ll i = h[now]; i; i = wh[i].h)
	{
		if(wh[i].w == Fa[now] || wh[i].w == son[now])
			continue;
		DFS2(wh[i].w, wh[i].w);
	}
	return;
}

void Findd(ll x, ll y)
{
	ll ans = 0;
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])swap(x, y);
		ans += Summ(1, 1, n, uid[top[x]], uid[x]);
		x = Fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	ans += Summ(1, 1, n, uid[x], uid[y]);
	if(ans < 0)putchar('-');
	write(abs(ans));
	putchar('\n');
	return;
}

void MaxFind(ll x, ll y)
{
	ll ans = -1e17;
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])swap(x, y);
		ans = max(ans, MaxFindd(1, 1, n, uid[top[x]], uid[x]));
		x = Fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	ans = max(ans, MaxFindd(1, 1, n, uid[x], uid[y]));
	if(ans < 0)putchar('-');
	write(abs(ans));
	putchar('\n');
	return;
}

int main()
{
	n = read();
	ll x, y;
	for(ll i = 1; i < n; ++i)
	{
		x = read(), y = read();
		hw(x, y), hw(y, x);
	}
	for(ll i = 1; i <= n; ++i)Z[i] = read();
	num = 0;
	DFS1(1, 0);
	DFS2(1, 1);
	build(1, 1, n);
	ll k, xxx;
	char ss[1005];
	Q = read();
	while(Q--)
	{
		scanf("%s", ss);
		if(ss[0] == 'C')
		{
			x = read(), k = read();
			Add(1, 1, n, uid[x], uid[x], k);
		}
		else if(ss[1] == 'M')
		{
			x = read(), y = read();
			MaxFind(x, y);
		}
		else if(ss[1] == 'S')
		{
			x = read(), y = read();
			Findd(x, y);
		}
	}
	return 0;
}