QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#662698 | #9492. 树上简单求和 | Hanghang | 0 | 2056ms | 74184kb | C++20 | 2.0kb | 2024-10-21 09:19:31 | 2024-10-21 09:19:33 |
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;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%