QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662698#9492. 树上简单求和Hanghang0 2056ms74184kbC++202.0kb2024-10-21 09:19:312024-10-21 09:19:33

Judging History

This is the latest submission verdict.

  • [2024-10-21 09:19:33]
  • Judged
  • Verdict: 0
  • Time: 2056ms
  • Memory: 74184kb
  • [2024-10-21 09:19:31]
  • 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;bel[i]=(i-1)/B+1;
	}
	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";
	}
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 23872kb

input:

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

output:

16015909870325688981
8612668651179921537
11254276556947476359
6249136646218181689
13203276385805639615
14699845850441820631
14770066505135687110
10296979023981987899
14075562401655819455
14511060705608422213
15540161041574278675
3401528614612004498
9436886767007745934
3291898860966641700
15358809130...

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: 2056ms
memory: 46588kb

input:

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

output:

8895986667946264907
18049578730233697046
6982484999433263032
2641000093197056571
11490995841603467718
7430823975660159877
1328067408904278458
13790196793094757622
17077305500424407036
15312008448535000819
1575844322639391163
16087829494670438241
17034638867115634776
13331933398430609112
766246997992...

result:

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

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 884ms
memory: 68684kb

input:

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

output:

12269764872054650519
9706181907138473261
6658082412335784406
6553176947521976605
17897387397966303050
15350505815517559756
9255543407945989195
10121860709749656846
14226135411897412028
10098163809434069503
7566612408972247054
5962461292353207443
10710295104347495167
13252040036705951666
888277105711...

result:

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

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 1286ms
memory: 74184kb

input:

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

output:

10967761149958330853
8139981573061880400
3490103963979582141
1300067635155283081
7598100649177376831
4763609486956692226
739614203503170664
3443465129341784676
10846816038772350927
13006595379146442618
18287718584034614257
14071548294707962000
8701574159694735265
17109015116000038327
107720717281346...

result:

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

Subtask #7:

score: 0
Skipped

Dependency #1:

0%