QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#662320 | #9492. 树上简单求和 | Kevin5307 | 0 | 0ms | 0kb | C++23 | 4.3kb | 2024-10-20 22:51:12 | 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;
}
详细
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%