C++(g++ 7.5.0) 解法, 执行用时: 268ms, 内存消耗: 7904K, 提交时间: 2023-04-19 13:24:52

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using i64 = long long;
using pii = pair<ll,ll>;
#define endl '\n'
#define ls u<<1
#define rs u<<1|1
//#define int __int128
//#define int long long
const int mod = 1e9+7;
const int N = 2e5+10;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
template<class T>
T lowbit(T x){return x&-x;}
int n,m,k;
void ios__stdio();
int e[N],ne[N],w[N],idx,h[N],top[N],hs[N],sz[N],f[N],tot,dfn[N],id[N];
int dep[N];
ll a[N];
struct segtree
{
	int l,r;
	ll sum,umax;
}tr[N<<2];
void push_up(int u)
{
	tr[u].sum=tr[ls].sum+tr[rs].sum;
	tr[u].umax=max(tr[ls].umax,tr[rs].umax);
}
void build(int u,int l,int r)
{
	if(l==r) tr[u]={l,r,a[id[l]],a[id[l]]};
	else
	{
		tr[u]={l,r,0,-INF};
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		push_up(u);
	}
}
void modify(int u,int x,int v)
{
	if(tr[u].l==x&&tr[u].r==x) tr[u].sum=tr[u].umax=v;
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) modify(ls,x,v);
		else modify(rs,x,v);
		push_up(u);
	}
}
pii getval(pii p1,pii p2)
{
	return {p1.first+p2.first,max(p1.second,p2.second)};
}
pii query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return {tr[u].sum,tr[u].umax};
	else
	{
		pii res={0,-INF};
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) res=getval(res,query(ls,l,r));
		if(r>mid) res=getval(res,query(rs,l,r));
		return res;
	}
}
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int fa)
{
	sz[u]=1;
	dep[u]=dep[fa]+1;
	hs[u]=-1;
	f[u]=fa;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		dfs1(j,u);
		sz[u]+=sz[j];
		if(hs[j]==-1||sz[j]>sz[hs[u]]) hs[u]=j;
	}
}
void dfs2(int u,int t)
{
	dfn[u]=++tot;
	top[u]=t;
	id[tot]=u;
	if(hs[u]!=-1)
	{
		dfs2(hs[u],t);
	}
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==f[u]||hs[u]==j) continue;
		dfs2(j,j);
	}
}
pii ask(int x,int y)
{
	pii res={0,-INF};
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=getval(res,query(1,dfn[top[x]],dfn[x]));
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=getval(res,query(1,dfn[x],dfn[y]));
	return res;
}

void solve()
{
	cin>>n;
	memset(h,-1,sizeof h);
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}	
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,tot);
	cin>>m;
	while(m--)
	{
		string op;
		int l,r;
		cin>>op>>l>>r;
		if(op=="QMAX")
		{
			auto res=ask(l,r);
			cout<<res.second<<endl;
		}
		else if(op=="QSUM")
		{
			auto res=ask(l,r);
			cout<<res.first<<endl;
		}
		else
		{
			modify(1,dfn[l],r);
		}
	}
}
int main()
{
	ios__stdio();
	int t=1;	
	//freopen("a.txt'","r",stdin);
	//cin>>t;
	while(t--) solve();
}
void ios__stdio()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
}

C++(clang++ 11.0.1) 解法, 执行用时: 279ms, 内存消耗: 4932K, 提交时间: 2023-01-02 23:56:06

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct cc{
	int to,nex;
}e[maxn],dis[maxn];
int head[maxn],cnt1,h[maxn],cnt2;
void add1(int u,int v)//原树边 
{
	++cnt1;
	e[cnt1].to=v;
	e[cnt1].nex=head[u];
	head[u]=cnt1;
}
void add2(int u,int v)//分块后块内树边 
{
	++cnt2;
	dis[cnt2].to=v;
	dis[cnt2].nex=h[u];
	h[u]=cnt2;
}
int rt[maxn],mx[maxn],sum[maxn],siz[maxn];
int n,m,v[maxn],deep[maxn],len,fa[maxn];
void dfs(int u,int f,int dep)
{
	deep[u]=dep;
	int tmp=rt[u];
	fa[u]=f;
	for(int i=head[u];i;i=e[i].nex)
	{
		int v=e[i].to;
		if(v!=f)
		{
			if(siz[tmp]+1<len)
			{
				add2(u,v);//块内树连边 
				rt[v]=tmp;
				++siz[tmp];
			}
			dfs(v,u,dep+1);
		}
	}
}
void build(int u,int num,int vmx)//维护当前节点，到块内根节点的和，最大值
{
	num+=v[u],sum[u]=num;
	vmx=max(vmx,v[u]),mx[u]=vmx;
	for(int i=h[u];i;i=dis[i].nex)
		build(dis[i].to,num,vmx);
} 
int query(int a,int b,int tag)
{
	int ans1=0;//QSUM
	int ans2=-(1<<30);//QMAX
	while(a!=b)//类似于倍增，只不过这里的距离为sqrt(n) 
	{
		if(deep[a]<deep[b]) swap(a,b);
		if(rt[a]==rt[b])//若所属同一个块
		{
			ans1+=v[a];
			ans2=max(ans2,v[a]);
			a=fa[a];//由于在同一块内，暴力跳的复杂度只为O(sqrt(n)) 
		} 
		else
		{
			if(deep[rt[a]]<deep[rt[b]]) swap(a,b);//块的深度更深 
			ans1+=sum[a];
			ans2=max(ans2,mx[a]);
			a=fa[rt[a]];//直接跳一个块 
		}
	}
	ans1+=v[a];
	ans2=max(ans2,v[a]);//更新它们的LCA的值 
	if(tag==0) return ans2;
	else return ans1; 
} 
void change(int u,int x)
{
	v[u]=x;
	if(u==rt[u]) build(u,0,-(1<<30));//如果是块内根节点就整个块更新
	else build(u,sum[fa[u]],mx[fa[u]]);//如果不是，就从其父亲开始更新
}
int main()
{
	int x,y;
	scanf("%d",&n);
	len=sqrt(n);
	for(int i=1;i<n;++i)
		scanf("%d%d",&x,&y),add1(x,y),add1(y,x);//原树边 
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]),rt[i]=i;
	dfs(1,0,0);
	for(int i=1;i<=n;++i)
		if(rt[i]==i) 
			build(i,0,-(1<<30));
	scanf("%d",&m);
	char opt[30];
	for(int i=1;i<=m;++i)
	{
		scanf("%s%d%d",opt,&x,&y);
		if(opt[1]=='M')//QMAX
			printf("%d\n",query(x,y,0));//01维护询问问题 
		else if(opt[1]=='S')//QSUM
			printf("%d\n",query(x,y,1));//01维护询问问题 
		else //CHANGE 
			change(x,y);
	}
	return 0;
}