WA求助,样例过不了
查看原帖
WA求助,样例过不了
180106
Kirie_LingKui楼主2020/11/23 22:09

RT,代码如下

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<cstdio>
#define R(i,a,n) for(register long long i=(a);i<=(n);i++)
#define F(i,a,n) for(register long long i=(n);i>=(a);i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> void read(T &x) {
	x = 0; int f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {f |= (ch == '-'); ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	x = f ? -x : x;
	return;
}
using namespace std;
const ll maxn=1e5+10;
struct edge{ll nex,to;}e[2*maxn];
struct note{ll l,r,sum,add;}a[maxn*2];
ll n,m,r,rt,mod,v[maxn],head[maxn],cnt,f[maxn],d[maxn],son[maxn],size[maxn],top[maxn],id[maxn],rk[maxn];
void build(ll u,ll v){e[++cnt].nex=head[u];e[cnt].to=v;head[u]=cnt;}
void dfs1(ll x,ll fa,ll depth)
{
	f[x]=fa;size[x]=1;d[x]=depth;
	for(int i=head[x];i;i=e[i].nex)
	{
		ll y=e[i].to;
		if(y==fa) continue;
		dfs1(y,x,depth+1);
		size[x]+=size[y];
		if(size[son[x]]<size[y]) son[x]=y;
	}
}
void dfs2(ll x,ll tp)
{
	top[x]=tp;id[x]=++cnt;rk[cnt]=x;
	if(son[x]) dfs2(son[x],tp);
	for(ll i=head[x];i;i=e[i].nex)
	{
		ll y=e[i].to;
		if(son[x]!=y&&y!=f[x])dfs2(y,y);
	}
}
void pup(ll x)
{
	a[x].sum=a[2*x].sum+a[2*x+1].sum;
}
void built(ll l,ll r,ll x)
{
	a[x].l=l;a[x].r=r;
	if(l==r)
	{
		a[x].sum=0;
		return ;
	}
	ll mid=(l+r)>>1;
	built(l,mid,2*x);built(mid+1,r,2*x+1);
	pup(x);
	return ;
}
ll len(ll x)
{
	return a[x].r-a[x].l+1;
}
void spread(ll x)
{
	if(a[x].add)
	{
		ll ls=2*x,rs=2*x+1,lz=a[x].add;
		a[ls].sum+=len(ls)*lz;a[rs].sum+=len(rs)*lz;
		a[ls].add+=lz;a[rs].add+=lz;
		a[x].add=0;
	}
}
void change(ll l,ll r,ll c,ll x)
{
	if(a[x].l>=l&&a[x].r<=r)
	{
		a[x].sum+=len(x)*c;
		a[x].add+=c;
		return ;
	}
	spread(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(l<=mid) change(l,r,c,2*x);
	if(r>mid) change(l,r,c,2*x+1);
	pup(x); return ;
}
ll ask(ll l,ll r,ll x)
{
	if(a[x].l>=l&&a[x].r<=r)
	{
		return a[x].sum;
	}
	spread(x);
	ll mid=(a[x].l+a[x].r)>>1,ans=0;
	if(l<=mid) ans+=ask(l,r,2*x);
	if(r>mid)  ans+=ask(l,r,2*x+1);
	return ans;
}
void lcasum(ll x,ll y,ll c)
{
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		change(id[top[x]],id[x],c,1);
		x=f[top[x]];
	}
	if(d[x]<d[y]) swap(x,y);
	change(rk[y],rk[x],c,1);
}
/*void ModifyOnTree(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		modify(rk[top[x]],rk[x],1,k);x=fa[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	modify(rk[y],rk[x],1,k);
}*/
ll asktree(ll x,ll y)
{
	ll ans=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		ans+=ask(rk[top[x]],rk[x],1);
		x=f[top[x]];
	}
	if(id[x]<id[y]) swap(x,y);
	ans+=ask(rk[y],rk[x],1);
	return ans;
}
int main()
{
	read(n);
	R(i,1,n-1)
	{
		ll x,y;
		read(x);read(y);
		build(x,y);build(y,x);
	}
	dfs1(0,0,1);cnt=0;dfs2(0,0);built(1,n,1);
	read(m);
	R(i,1,m)
	{
		char op;
		cin>>op;
		if(op=='A')
		{
			ll u,v,c;
			read(u);read(v);read(c);
			lcasum(u,v,c);
		}
		else
		{
			ll x;
			read(x);
			printf("%d\n",ask(id[x],id[x]+size[x]-1,1));
		}
	}
	return 0;
}

2020/11/23 22:09
加载中...