QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662714#9492. 树上简单求和Hanghang0 2097ms75484kbC++202.0kb2024-10-21 09:25:582024-10-21 09:25:59

Judging History

This is the latest submission verdict.

  • [2024-10-21 09:25:59]
  • Judged
  • Verdict: 0
  • Time: 2097ms
  • Memory: 75484kb
  • [2024-10-21 09:25:58]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
const int N=2e5+3;
struct Tree
{
	int dep[N],fa[N],sz[N],hson[N];
	int tim,dfn[N],pos[N],top[N];
	vector<int>ve[N];
	void Dfs1(int x)
	{
		dep[x]=dep[fa[x]]+1;sz[x]=1;
		for(int y:ve[x])if(y!=fa[x])
		{
			fa[y]=x;Dfs1(y);sz[x]+=sz[y];
			if(sz[hson[x]]<sz[y])hson[x]=y;
		}
	}
	void Dfs2(int x,int tp)
	{
		top[x]=tp;dfn[++tim]=x;pos[x]=tim;
		if(hson[x])Dfs2(hson[x],tp);
		for(int y:ve[x])if(y!=fa[x]&&y!=hson[x])Dfs2(y,y);
	}
	auto Get(int x,int y)
	{
		vector<array<int,2>>res; 
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			res.pb({pos[x],1});res.pb({pos[fa[x]]-1,-1});
			x=fa[top[x]];
		}
		if(dep[x]<dep[y])swap(x,y);
		res.pb({pos[x],1});res.pb({pos[y]-1,-1});
		return res;
	}
	void Init(int n)
	{
		for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].pb(y),ve[y].pb(x);
		Dfs1(1);Dfs2(1,1);
	}
}T1,T2;
const int B=512;
int n,m,bel[N],p[N],q[N],res[B][B];
ull a[N],b[N],sum[N],tag[N];
void Upd(int x,ull z)
{
	int bx=bel[x];
	for(int i=(bx-1)*B+1;i<=x;i++)a[p[i]]+=z,sum[bel[p[i]]]+=z;
	if(!--bx)return;
	for(int i=1;i<=bx;i++)tag[i]+=z;
	for(int i=1;i<=bel[n];i++)sum[i]+=res[bx][i]*z;
}
ull Ask(int x)
{
	int bx=bel[x];ull s=0;
	for(int i=1;i<bx;i++)s+=sum[i];
	for(int i=(bx-1)*B+1;i<=x;i++)s+=a[i]+tag[bel[q[i]]];
	return s; 
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>b[i];
	T1.Init(n);T2.Init(n);
	for(int i=1;i<=n;i++)
	{
		int x=T1.pos[i],y=T2.pos[i];
		a[y]=b[i];p[x]=y;q[y]=x;
	}
	for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1,sum[bel[i]]+=a[i];
	for(int i=1;i<=n;i++)res[bel[i]][bel[p[i]]]++;
	for(int i=1;i<=bel[n];i++)for(int j=1;j<=bel[n];j++)res[i][j]+=res[i-1][j];
	while(m--)
	{
		int x,y;ull z,ans=0;cin>>x>>y>>z;
		auto s1=T1.Get(x,y),s2=T2.Get(x,y);
		for(auto t:s1)if(t[0])Upd(t[0],t[1]*z);
		for(auto t:s2)if(t[0])ans+=Ask(t[0])*t[1];
		cout<<ans<<"\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 28696kb

input:

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

output:

16015909870325688981
8612668651179921537
17631005735732382346
6249136646218181689
8796390826555158605
14699845850441820631
14770066505135687110
10296979023981987899
1708478074531102353
10104175146357941203
15540161041574278675
3401528614612004498
9436886767007745934
5329484579975069766
1535880913016...

result:

wrong answer 1st lines differ - expected: '12105153858659381124', found: '16015909870325688981'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 2097ms
memory: 47336kb

input:

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

output:

8895986667946264907
18049578730233697046
6982484999433263032
2641000093197056571
3643767143815855507
7430823975660159877
8852183786315847628
13790196793094757622
9636954657724053495
12650505395327410603
1575844322639391163
12599252777493376200
17034638867115634776
13331933398430609112
13892581952872...

result:

wrong answer 1st lines differ - expected: '9042998055336671259', found: '8895986667946264907'

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 907ms
memory: 67144kb

input:

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

output:

14268231842344887732
10313945044528890202
1298826501001616879
8823385713645132818
6333705739224743139
9439924794281172322
7783751703118023897
16561070230834850485
15327319976703122164
2995765806665642369
2631810405817962789
7044031694063215157
12722342025283134005
3157959957131131402
111122741599868...

result:

wrong answer 1st lines differ - expected: '11479812171669345085', found: '14268231842344887732'

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 1283ms
memory: 75484kb

input:

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

output:

11310632323096036652
12390040481641715652
15682103576618265620
13264000400962994828
257739039453848625
14179199497203804081
790925800268469739
1583945302857281077
15568192198235363893
13159488718792204722
11188416629623592070
3835058837077710746
5355136090056108415
2326426441397915855
85163952761146...

result:

wrong answer 1st lines differ - expected: '5519324519442957729', found: '11310632323096036652'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%