QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743798 | #7767. 数据结构 | Larunatrecy | 20 | 767ms | 154640kb | C++14 | 6.1kb | 2024-11-13 20:02:59 | 2024-11-13 20:03:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
x=(f?-x:x);
}
typedef unsigned long long ull;
const int N = 2e5+7;
typedef long long LL;
int n;
vector<int> G[N],T[N];
int fa[N],siz[N],son[N],dfn[N],dep[N],top[N],seq[N],tot=0;
void dfs(int x,int pre)
{
fa[x]=pre;siz[x]=1;dep[x]=dep[pre]+1;
for(int y:T[x])if(y!=pre)
{
dfs(y,x);
siz[x]+=siz[y];
G[x].push_back(y);
if(siz[y]>siz[son[x]])son[x]=y;
}
}
struct BIT
{
ull d[N],c[N];
void add1(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)d[i]+=v;}
void add2(int x,ull v){for(int i=x;i<=n+1;i+=i&-i)c[i]+=v;}
ull ask1(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
ull ask2(int x){ull res=0;for(int i=x;i;i-=i&-i)res+=c[i];return res;}
inline ull sum(int x){return ask1(x)*(x+1)-ask2(x);}
inline void add(int l,int r,ull v)
{if(l>r)return;//printf("add:[%d,%d]\n",l,r);
add1(l,v);add1(r+1,-v);add2(l,v*l);add2(r+1,-v*(r+1));}
inline ull ask(int l,int r)
{
if(l>r)return 0;//printf("ask:[%d,%d]\n",l,r);
return sum(r)-sum(l-1);}
}DS;
void extend(int x,int t)
{
if(!dfn[x])seq[dfn[x]=++tot]=x;
if(!t)return;
for(int y:G[x])extend(y,t-1);
}
void dfs2(int x,int topth)
{
top[x]=topth;
if(x==topth)
{
for(int i=0;i<=3;i++)
for(int u=x;u;u=son[u])extend(u,i);
}
if(!son[x])return;
dfs2(son[x],topth);
for(int y:G[x])if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define l(x) x.first
#define r(x) x.second
#define segment vector<pii>
segment operator +(segment A,segment B)
{
if(A.empty())return B;
if(B.empty())return A;
segment C;
int i=0,j=0,l=-1;
while(i<(int)A.size()||j<(int)B.size())
{
pii cur;
if(j>=(int)B.size()||(i<(int)A.size()&&A[i].first<B[j].first))
cur=A[i++];
else cur=B[j++];
if(l(cur)==l+1)C.back().second=cur.second;
else C.push_back(cur);
l=cur.second;
}
return C;
}
segment tree[N];
void dfs3(int x,int pre)
{
tree[x].push_back(mk(dfn[x],dfn[x]));
for(int y:G[x])
{
dfs3(y,x);
tree[x]=tree[x]+tree[y];
}
}
segment A[N][4],W[N][4];
bool vis[N];
segment S;
void get(int x,int d)
{
segment cur;cur.push_back({dfn[x],dfn[x]});
if(!d){S=S+cur;return;}
for(int y:G[x])if(!vis[y])get(y,d-1);
}
void dfs4(int x)
{
for(int d=0;d<=3;d++)
{
S.clear();
get(x,d);
W[x][d]=S;
}
if(x==top[x])
{
for(int u=x;u;u=son[u])vis[u]=1;
for(int d=0;d<=3;d++)
{
S.clear();
for(int u=x;u;u=son[u])
{
get(u,d);
if(d)A[u][d]=A[u][d-1];
A[u][d]=A[u][d]+S;
}
}
for(int u=x;u;u=son[u])vis[u]=1;
}
if(!son[x])return;
dfs4(son[x]);
for(int y:G[x])if(y!=son[x])
dfs4(y);
}
void apply(int x,int k,ull v)
{
int lst=x;
for(int i=1;i<=k;i++)
{
lst=x;
x=fa[x];
if(!x)return;
for(auto u:W[x][k-i])DS.add(l(u),r(u),v);
if(i<k)for(auto u:W[lst][k-i-1])DS.add(l(u),r(u),-v);
}
}
void modify(int x,int y,int k,int v)
{
int lstx=0,lsty=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
for(auto u:A[x][k])DS.add(l(u),r(u),v);
if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
if(son[x]&&k)for(auto u:W[son[x]][k-1])DS.add(l(u),r(u),v);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
for(auto u:A[y][k])DS.add(l(u),r(u),v);
if(x!=top[x])
for(auto u:A[fa[x]][k])DS.add(l(u),r(u),-v);
if(lstx&&k)for(auto u:W[lstx][k-1])DS.add(l(u),r(u),-v);
if(lsty&&k)for(auto u:W[lsty][k-1])DS.add(l(u),r(u),-v);
if(son[y]&&k)for(auto u:W[son[y]][k-1])DS.add(l(u),r(u),v);
if(k)apply(x,k,v);
}
ull getans(int x,int k)
{
ull res=0;
int lst=x;
for(int i=1;i<=k;i++)
{
lst=x;
x=fa[x];
if(!x)break;
for(auto u:W[x][k-i])res+=DS.ask(l(u),r(u));
if(i<k)for(auto u:W[lst][k-i-1])res-=DS.ask(l(u),r(u));
}
return res;
}
ull query(int x,int y,int k)
{
ull res=0;
int lstx=0,lsty=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y),swap(lstx,lsty);
for(auto u:A[x][k])res+=DS.ask(l(u),r(u));
if(lstx&&k)for(auto u:W[lstx][k-1])res-=DS.ask(l(u),r(u));
if(son[x]&&k)for(auto u:W[son[x]][k-1])res+=DS.ask(l(u),r(u));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y),swap(lstx,lsty);
for(auto u:A[y][k])res+=DS.ask(l(u),r(u));
if(x!=top[x])
for(auto u:A[fa[x]][k])res-=DS.ask(l(u),r(u));
if(lstx&&k)for(auto u:W[lstx][k-1])res-=DS.ask(l(u),r(u));
if(lsty&&k)for(auto u:W[lsty][k-1])res-=DS.ask(l(u),r(u));
if(son[y]&&k)for(auto u:W[son[y]][k-1])res+=DS.ask(l(u),r(u));
if(k)res+=getans(x,k);
return res;
}
int main()
{
int m;
read(n);read(m);
for(int i=1;i<n;i++)
{
int u,v;
read(u);read(v);
T[u].push_back(v);
T[v].push_back(u);
}
dfs(1,0);dfs2(1,1);
dfs3(1,0);dfs4(1);
while(m--)
{
int op,x,y,k,v;
read(op);
if(op==1)
{
read(x);read(y);read(k);read(v);
modify(x,y,k,v);
}
else if(op==2)
{
read(x);read(v);
for(auto u:tree[x])DS.add(l(u),r(u),v);
}
else if(op==3)
{
read(x);read(y);read(k);
printf("%lld\n",query(x,y,k));
}
else if(op==4)
{
read(x);
ull res=0;
for(auto u:tree[x])res+=DS.ask(l(u),r(u));
printf("%lld\n",res);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 17ms
memory: 62144kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
34981763088 2131932638802 2793343744484 1305552349474 1692496631038 2677934645348 6683382085629 2081426057982 5784732544789 2186592622 4013940978092 1674542130 6524658548 7090115254775 10048023011004 11578510707076 492570862 3325092033836 2834694279 4189252521026 4395772262 4221137767 9630829210 991...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '34981763088'
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 647ms
memory: 121608kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 10
Accepted
time: 700ms
memory: 128144kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 276ms
memory: 154640kb
input:
200000 200000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 ...
output:
0 134314511981213 38210069287857 75884072418736 25202420957824 179526731139183 75824457254155 156951554536901 246509099341609 251382675444241 181645863942433 285463128028270 213786734389331 244905818158545 53373845240870 448431934080 379302811856289 720756746262595 768643901209812 224740493575747 18...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '134314511981213'
Subtask #4:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 635ms
memory: 121724kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99786 numbers
Test #8:
score: 10
Accepted
time: 456ms
memory: 138244kb
input:
200000 200000 1 2 2 3 1 4 1 5 2 6 3 7 6 8 8 9 8 10 9 11 8 12 12 13 13 14 11 15 13 16 13 17 16 18 17 19 18 20 19 21 19 22 21 23 21 24 21 25 24 26 23 27 26 28 27 29 26 30 30 31 28 32 29 33 32 34 32 35 33 36 36 37 35 38 38 39 38 40 40 41 39 42 42 43 43 44 41 45 45 46 43 47 45 48 46 49 49 50 50 51 51 52...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100404 numbers
Test #9:
score: 10
Accepted
time: 661ms
memory: 128076kb
input:
200000 200000 166945 2 60190 3 101888 4 154621 5 188595 6 175999 7 140051 8 54071 9 167394 10 54228 11 48270 12 14564 13 25727 14 138072 15 77670 16 77795 17 155644 18 171648 19 94412 20 65323 21 130225 22 6359 23 17410 24 8580 25 142556 26 152863 27 166869 28 115234 29 87099 30 160349 31 98200 32 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99768 numbers
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #10:
score: 0
Wrong Answer
time: 647ms
memory: 121628kb
input:
200000 200000 1 2 1 3 2 4 1 5 2 6 2 7 2 8 5 9 3 10 10 11 5 12 4 13 5 14 9 15 11 16 14 17 12 18 13 19 2 20 16 21 3 22 16 23 2 24 7 25 8 26 20 27 21 28 11 29 12 30 4 31 2 32 21 33 14 34 29 35 16 36 21 37 28 38 22 39 27 40 12 41 36 42 32 43 30 44 3 45 43 46 4 47 14 48 44 49 9 50 37 51 20 52 11 53 31 54...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 348th numbers differ - expected: '1896761708', found: '948380854'
Subtask #6:
score: 0
Skipped
Dependency #4:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #17:
score: 0
Wrong Answer
time: 767ms
memory: 121708kb
input:
200000 200000 1 2 1 3 3 4 1 5 2 6 3 7 1 8 5 9 6 10 9 11 2 12 8 13 3 14 4 15 12 16 10 17 2 18 2 19 14 20 12 21 9 22 19 23 14 24 3 25 13 26 21 27 11 28 5 29 9 30 13 31 13 32 4 33 6 34 14 35 14 36 31 37 13 38 10 39 4 40 28 41 13 42 14 43 20 44 37 45 8 46 14 47 32 48 21 49 40 50 46 51 20 52 44 53 15 54 ...
output:
0 16849806164 0 0 9237014108 14980842797 14547193369 0 34620785077 28582135084 9536184858 0 50602196510 63751565995 0 0 0 0 0 17909528605 29097444027 15784168183 63602284518 103641568247 0 27410235941 24210040197 0 0 1662166464 28413282125 0 28484661570 226875881433 0 100259074982 175344184178 28518...
result:
wrong answer 2nd numbers differ - expected: '12712803164', found: '16849806164'
Subtask #8:
score: 0
Skipped
Dependency #1:
0%