原 地 暴 毙
  • 板块学术版
  • 楼主wuyue2005
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/6/14 13:02
  • 上次更新2023/11/7 00:40:38
查看原帖
原 地 暴 毙
94963
wuyue2005楼主2020/6/14 13:02

树的统计照着题解敲的板子似乎越界了,求解……我可能瞎了

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long maxn=200010;
long long n,m,e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn],a[maxn<<2],b[maxn<<2],son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn],res=0;
inline void add(long long x,long long y)
{
	to[++e]=y;
	nex[e]=beg[x];
	beg[x]=e;
}
inline void build(long long rt,long long l,long long r)
{
	if(l==r)
	{
		a[rt]=wt[l];
		b[rt]=wt[l];
		return ;
	}
	build(rt<<1,l,((l+r)>>1));
	build(rt<<1|1,((l+r)>>1)+1,r);
	a[rt]=a[rt<<1]+a[rt<<1|1];
	b[rt]=max(b[rt<<1],b[rt<<1|1]);
}
inline void query(long long rt,long long l,long long r,long long L,long long R)
{
	if(L<=l&&r<=R)
	{
		res+=a[rt];
		return ;
	}
	else{
		if(L<=((l+r)>>1)) query(rt<<1,l,((l+r)>>1),L,R);
		if(R>((l+r)>>1)) query(rt<<1|1,((l+r)>>1)+1,r,L,R);
	}
}
inline void quemax(long long rt,long long l,long long r,long long L,long long R)
{
	if(L<=l&&r<=R)
	{
		res=max(b[rt],res);
		return ;
	}
	else
	{
		if(L<=((l+r)>>1)) quemax(rt<<1,l,((l+r)>>1),L,R);
		if(R>((l+r)>>1)) quemax(rt<<1|1,((l+r)>>1)+1,r,L,R);
	}
}
inline void update(long long rt,long long l,long long r,long long L,long long R,long long k)
{
	if(L<=l&&r<=R)
	{
		a[rt]=k;
		b[rt]=k;
	}
	else
	{
		if(L<=((l+r)>>1)) update(rt<<1,l,((l+r)>>1),L,R,k);
		if(R>((l+r)>>1)) update(rt<<1|1,((l+r)>>1)+1,r,L,R,k);
		a[rt]=(a[rt<<1]+a[rt<<1|1]);
		b[rt]=max(b[rt<<1],b[rt<<1|1]);
	}
}
inline long long qRange(long long x,long long y)
{
	long long ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res=0;
		query(1,1,n,id[top[x]],id[x]);
		ans+=res;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	res=0;
	query(1,1,n,id[x],id[y]);
	ans+=res;
	return ans;
}
inline long long qMax(long long x,long long y)
{
	long long ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=0;
		quemax(1,1,n,id[top[x]],id[x]);
		ans=max(ans,res);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=0;
	quemax(1,1,n,id[x],id[y]);
	ans=max(ans,res);
	return ans;
}
inline void updSon(long long x,long long k) {update(1,1,n,id[x],id[x],k);}
inline void dfs1(long long x,long long f,long long deep)
{
	dep[x]=deep;
	fa[x]=f;
	siz[x]=1;
	long long maxson=-1;
	for(register long long i=beg[x];i;i=nex[i])
	{
		long long y=to[i];
		if(y==f) continue;
		dfs1(y,x,deep+1);
		siz[x]+=siz[y];
		if(siz[y]>maxson)
		{
			son[x]=y,maxson=siz[y];
		} 
	}
}
inline void dfs2(long long x,long long topf)
{
	id[x]=++cnt;
	wt[cnt]=w[x];
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for(register long long i=beg[x];i;i=nex[i])
	{
		long long y=to[i];
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
int main()
{
	scanf("%lld",&n);
	for(register long long i=1;i<n;i++)
	{
		long long a,b;
		scanf("%lld%lld",&a,&b);
		add(a,b);add(b,a);
	}
	for(register long long i=1;i<=n;i++) scanf("%lld",&w[i]);
	dfs1(1,1,1);
	dfs2(1,1);
	build(1,1,n);
	scanf("%lld",&m);
	while(m--)
	{
		long long x,y;
		char k[10];
		cin>>k;
		if(k[1]=='H')
		{
			scanf("%lld%lld",&x,&y);
			updSon(x,y);
		}
		else if(k[1]=='S')
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",qRange(x,y));
		}
		else
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",qMax(x,y));
		}
	}
	return 0;
}
2020/6/14 13:02
加载中...