求调p3833 50pts
  • 板块学术版
  • 楼主jxjxmmm
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/26 19:00
  • 上次更新2024/3/26 19:20:15
查看原帖
求调p3833 50pts
1075700
jxjxmmm楼主2024/3/26 19:00
#include<bits/stdc++.h>
using namespace std;
#define lu u<<1
#define ru u<<1|1
#define int long long
int n,q,tim;
int lazy[100010<<2],sum[100010<<2],dep[100010<<2],fa[100010<<2];
int son[100010<<2],siz[100010<<2],dfn[100010<<2],top[100010<<2];
vector<int> G[100010];
void dfs1(int u)
{
	siz[u]=1;
	for(int i=0;i<(int)G[u].size();i++)
	{
		dep[G[u][i]]=dep[u]+1;
		dfs1(G[u][i]);
		siz[u]+=siz[G[u][i]];
		if(siz[son[u]]<siz[G[u][i]]) son[u]=G[u][i];
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	dfn[u]=++tim;
	if(son[u]) dfs2(son[u],tp);
	for(int i=0;i<(int)G[u].size();i++)
	{
		if(G[u][i]!=son[u]) dfs2(G[u][i],G[u][i]);
	}
}
void pushdown(int u,int l,int r)
{
	if(lazy[u])
	{
		int mid=(l+r)>>1;
		lazy[lu]+=lazy[u];
		lazy[ru]+=lazy[u];
		sum[lu]+=(mid-l+1)*lazy[u];
		sum[ru]+=(r-mid)*lazy[u];
		lazy[u]=0;
	}
}
void update(int u,int l,int r,int ql,int qr,int k)
{
	if(ql<=l&&qr>=r)
	{
		sum[u]+=(r-l+1)*k;
		lazy[u]+=k;
		return;
	}
	pushdown(u,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) update(lu,l,mid,ql,qr,k);
	if(qr>mid) update(ru,mid+1,r,ql,qr,k);
	sum[u]=sum[lu]+sum[ru];
}
void add(int u,int v,int k)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		update(1,1,n,dfn[top[u]],dfn[top[v]],k);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	update(1,1,n,dfn[v],dfn[u],k);
}
int query(int u,int l,int r,int ql,int qr)
{
	if(ql<=l&&qr>=r)
	{
		return sum[u];
	}
	pushdown(u,l,r);
	int ans=0,mid=(l+r)>>1;
	if(ql<=mid)
		ans=query(lu,l,mid,ql,qr);
	if(qr>mid)
		ans+=query(ru,mid+1,r,ql,qr);
	return ans;
}
signed main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	dep[1]=1;
	for(int i=1,a,b;i<n;i++)
	{
		cin>>a>>b;
		a++,b++;
		fa[b]=a;
		G[a].push_back(b);
	}
	dfs1(1);
	dfs2(1,1);
	string s;
	cin>>q;
	for(int i=1,u,v,d;i<=q;i++)
	{
		cin>>s;
		if(s=="A")
		{
			cin>>u>>v>>d;
			v++,u++;
			add(u,v,d);
		}
		else
		{
			cin>>u;
			u++;
			cout<<query(1,1,n,dfn[u],dfn[u]+siz[u]-1)<<'\n';
		}
	}
	return 0;
}
2024/3/26 19:00
加载中...