QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662714 | #9492. 树上简单求和 | Hanghang | 0 | 2097ms | 75484kb | C++20 | 2.0kb | 2024-10-21 09:25:58 | 2024-10-21 09:25:59 |
Judging History
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%