QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662320#9492. 树上简单求和Kevin53070 0ms0kbC++234.3kb2024-10-20 22:51:122024-10-20 22:51:12

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 22:51:12]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-10-20 22:51:12]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n,q;
ull a[200200];
vector<int> G1[200200],G2[200200];
int siz1[200200],siz2[200200];
int f1[200200],f2[200200];
int tp1[200200],tp2[200200];
int son1[200200],son2[200200];
int dfn1[200200],dfn2[200200];
int d1[200200],d2[200200];
int tot1,tot2;
void dfs1(int u,int fa,int *f,int *d,int *siz,int *son,vector<int> *G)
{
	f[u]=fa;
	d[u]=d[fa]+1;
	siz[u]=1;
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs1(v,u,f,d,siz,son,G);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])
				son[u]=v;
		}
}
void dfs2(int u,int fa,int *tp,int *son,int *dfn,int &tot,vector<int> *G)
{
	dfn[u]=++tot;
	if(!tp[u]) tp[u]=u;
	if(son[u])
	{
		tp[son[u]]=tp[u];
		dfs2(son[u],u,tp,son,dfn,tot,G);
	}
	for(auto v:G[u])
		if(v!=fa&&v!=son[u])
			dfs2(v,u,tp,son,dfn,tot,G);
}
int val[200200];
const int B=600;
ull c1[200200],c2[200200],ans[200200];
int x[200200],y[200200];
ull k[200200];
ull w[200200];
ull c3;
int psum[200200];
vector<pii> v1[200200],v2[200200];
int main()
{
	freopen("mist07.in","r",stdin);
	freopen("mist.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G1[u].pb(v);
		G1[v].pb(u);
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G2[u].pb(v);
		G2[v].pb(u);
	}
	dfs1(1,0,f1,d1,siz1,son1,G1);
	dfs2(1,0,tp1,son1,dfn1,tot1,G1);
	dfs1(1,0,f2,d2,siz2,son2,G2);
	dfs2(1,0,tp2,son2,dfn2,tot2,G2);
	for(int i=1;i<=n;i++)
		val[dfn1[i]]=dfn2[i];
	for(int i=1;i<=n;i++)
		w[dfn2[i]]=a[i];
	for(int i=1;i<=n;i++)
		w[i]+=w[i-1];
	for(int i=1;i<=q;i++)
		cin>>x[i]>>y[i]>>k[i];
	for(int i=1;i<=q;i++)
	{
		int u=x[i],v=y[i];
		while(tp1[u]!=tp1[v])
		{
			if(d1[tp1[u]]<d1[tp1[v]]) swap(u,v);
			v1[i].pb(dfn1[tp1[u]],dfn1[u]);
			u=f1[tp1[u]];
		}
		v1[i].pb(min(dfn1[u],dfn1[v]),max(dfn1[u],dfn1[v]));
	}
	for(int i=1;i<=q;i++)
	{
		int u=x[i],v=y[i];
		while(tp2[u]!=tp2[v])
		{
			if(d2[tp2[u]]<d2[tp2[v]]) swap(u,v);
			v2[i].pb(dfn2[tp2[u]],dfn2[u]);
			u=f2[tp2[u]];
		}
		v2[i].pb(min(dfn2[u],dfn2[v]),max(dfn2[u],dfn2[v]));
	}
	for(int i=1;i<=q;i++)
	{
		{
			auto solve=[&](int l,int r,ull k)->void
			{
				int lb=l/B;
				int rb=r/B;
				if(lb==rb)
				{
					for(int p=l;p<=r;p++)
					{
						c1[val[p]]+=k;
						c2[val[p]/B]+=k;
					}
				}
				else
				{
					for(int p=l;p<lb*B+B;p++)
					{
						c1[val[p]]+=k;
						c2[val[p]/B]+=k;
					}
					for(int p=r;p>=rb*B;p--)
					{
						c1[val[p]]+=k;
						c2[val[p]/B]+=k;
					}
				}
			};
			for(auto pr:v1[i])
				solve(pr.first,pr.second,k[i]);
		}
		{
			auto query=[&](int l,int r)->ull
			{
				ull ans=0;
				int lb=(l-1)/B;
				int rb=r/B;
				for(int i=lb;i<rb;i++)
					ans+=c2[i];
				for(int i=max(1,lb*B);i<l;i++)
					ans-=c1[i];
				for(int i=max(1,rb*B);i<=r;i++)
					ans+=c1[i];
				return ans+w[r]-w[l-1];
			};
			for(auto pr:v2[i])
				ans[i]+=query(pr.first,pr.second);
		}
	}
	for(int b=0;b<=n/B;b++)
	{
		c3=0;
		int L=max(1,b*B),R=min(n,b*B+B-1);
		memset(psum,0,sizeof(psum));
		for(int i=L;i<=R;i++)
			psum[val[i]]=1;
		for(int i=1;i<=n;i++)
			psum[i]+=psum[i-1];
		for(int i=1;i<=q;i++)
		{
			{
				auto solve=[&](int l,int r,ull k)->void
				{
					int lb=l/B;
					int rb=r/B;
					if(lb<b&&b<rb)
						c3+=k;
				};
				for(auto pr:v1[i])
					solve(pr.first,pr.second,k[i]);
			}
			{
				auto query=[&](int l,int r)->ull
				{
					return (psum[r]-psum[l-1])*c3;
				};
				for(auto pr:v2[i])
					ans[i]+=query(pr.first,pr.second);
			}
		}
	}
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

3000 3000
7236742292501328495 17973811477309806363 16075782662531676171 17971236571771878676 11392080645527132110 3685563455925680459 9773593720088356683 8313828403245053795 7736401634567449043 1634817828009987181 6951124933529719486 12775126714635387213 15460977209223753216 397573676785925632 31372...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Dangerous Syscalls

Test #21:

score: 0
Dangerous Syscalls

input:

200000 200000
622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...

output:


result:


Subtask #5:

score: 0
Dangerous Syscalls

Test #27:

score: 0
Dangerous Syscalls

input:

200000 200000
1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...

output:


result:


Subtask #6:

score: 0
Dangerous Syscalls

Test #34:

score: 0
Dangerous Syscalls

input:

200000 200000
6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%