QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61902 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | AFewSuns | 0 | 1704ms | 165884kb | C++14 | 5.8kb | 2022-11-15 21:20:19 | 2022-11-15 21:20:22 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
namespace my_std{
#define ll int
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 2e9
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define LC lc[x]
#define RC rc[x]
vector<pair<ll,ll> > q1[200020],q2[200020],q3[200020];
ll n,m,head[200020],cnt=0;
ll siz[200020],wson[200020],top[200020],f[200020],dep[200020];
ll rt[200020],tree[5000050],lc[5000050],rc[5000050],tot=0;
ll RT,rsiz,minn,tr[200020],num[200020];
bl ck[200020];
struct edge{
ll nxt,to;
}e[400040];
struct node{
ll x,y,lca,d,ans;
}q[200020];
void add(ll u,ll v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs1(ll fa,ll u){
f[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
go(u){
ll v=e[i].to;
if(v==fa) continue;
dfs1(u,v);
if(siz[v]>siz[wson[u]]) wson[u]=v;
siz[u]+=siz[v];
}
}
void dfs2(ll u,ll topp){
top[u]=topp;
if(wson[u]) dfs2(wson[u],topp);
go(u){
ll v=e[i].to;
if(v==f[u]) continue;
if(v!=wson[u]) dfs2(v,v);
}
}
ll get_lca(ll x,ll y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
void addtag(ll x,ll id,ll v){
if(!x) return;
q[id].ans+=v*dep[x];
if(wson[x]) q1[wson[x]].push_back(MP(id,v));
while(x){
q2[x].push_back(MP(id,v));
if(f[top[x]]){
q1[top[x]].push_back(MP(id,-v));
q1[wson[f[top[x]]]].push_back(MP(id,v));
}
x=f[top[x]];
}
}
void pushup(ll x){
tree[x]=tree[LC]+tree[RC];
}
void mdf(ll &x,ll l,ll r,ll pos){
if(!x) x=++tot;
if(l==r){
tree[x]++;
return;
}
ll mid=(l+r)>>1;
if(pos<=mid) mdf(LC,l,mid,pos);
else mdf(RC,mid+1,r,pos);
pushup(x);
}
ll query(ll x,ll l,ll r,ll ql,ll qr){
if(!x||ql>qr) return 0;
if(ql<=l&&r<=qr) return tree[x];
ll mid=(l+r)>>1,res=0;
if(ql<=mid) res+=query(LC,l,mid,ql,qr);
if(mid<qr) res+=query(RC,mid+1,r,ql,qr);
return res;
}
ll merge(ll x,ll y,ll l,ll r){
if(!x) return y;
if(!y) return x;
if(l==r){
tree[x]+=tree[y];
return x;
}
ll mid=(l+r)>>1;
LC=merge(LC,lc[y],l,mid);
RC=merge(RC,rc[y],mid+1,r);
pushup(x);
return x;
}
il ll lowbit(ll x){
return x&(-x);
}
il void mdf(ll x,ll v){
while(x<=n){
tr[x]+=v;
x+=lowbit(x);
}
}
il ll query(ll x){
ll res=0;
while(x){
res+=tr[x];
x-=lowbit(x);
}
return res;
}
void solve1(ll fa,ll u){
mdf(rt[u],1,n,dep[u]);
go(u){
ll v=e[i].to;
if(v==fa) continue;
solve1(u,v);
rt[u]=merge(rt[u],rt[v],1,n);
}
fr(i,0,(ll)q1[u].size()-1){
ll id=q1[u][i].fir,v=q1[u][i].sec;
if(!q[id].d) continue;
q[id].ans+=v*query(rt[u],1,n,1,min(n,dep[u]+q[id].d-1));
}
}
void dfs(ll fa,ll u,ll now,ll t){
mdf(now,t);
go(u){
ll v=e[i].to;
if(v==fa) continue;
dfs(u,v,now+1,t);
}
}
void solve2(ll fa,ll u){
go(u){
ll v=e[i].to;
if(v==fa) continue;
if(v!=wson[u]) dfs(u,v,1,1);
}
fr(i,0,(ll)q2[u].size()-1){
ll id=q2[u][i].fir,v=q2[u][i].sec;
q[id].ans+=v*query(min(n,q[id].d));
}
if(wson[u]) solve2(u,wson[u]);
go(u){
ll v=e[i].to;
if(v==fa) continue;
if(v!=wson[u]) dfs(u,v,1,-1);
}
}
void getroot(ll fa,ll u){
siz[u]=1;
ll maxx=0;
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
getroot(u,v);
siz[u]+=siz[v];
maxx=max(maxx,siz[v]);
}
maxx=max(maxx,rsiz-siz[u]);
if(maxx<minn){
minn=maxx;
RT=u;
}
}
void dfs3(ll fa,ll u){
siz[u]=1;
dep[u]=dep[fa]+1;
num[dep[u]]++;
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
dfs3(u,v);
}
}
void dfs4(ll r,ll fa,ll u,ll t){
fr(i,0,(ll)q3[u].size()-1){
ll id=q3[u][i].fir;
if(q[id].d>=dep[u]) q[id].ans+=num[min(siz[r],q[id].d-dep[u])];
}
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
dfs4(r,u,v,t);
}
}
void solve(ll fa,ll u){
ck[u]=1;
dep[u]=0;
num[0]++;
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
dfs3(u,v);
}
fr(i,1,siz[u]) num[i]+=num[i-1];
dfs4(u,fa,u,1);
fr(i,0,siz[u]) num[i]=0;
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
dfs3(u,v);
fr(j,1,siz[v]) num[j]+=num[j-1];
dfs4(v,u,v,-1);
fr(j,0,siz[v]) num[j]=0;
}
go(u){
ll v=e[i].to;
if(v==fa||ck[v]) continue;
minn=inf;
rsiz=siz[v];
getroot(u,v);
solve(u,v);
}
}
int main(){
// freopen("1.in","r",stdin);
// freopen("wa.out","w",stdout);
n=read();
fr(i,2,n){
ll u=read(),v=read();
add(u,v);
add(v,u);
}
dfs1(0,1);
dfs2(1,1);
m=read();
fr(i,1,m){
q[i].x=read();
q[i].y=read();
q[i].d=read();
q[i].lca=get_lca(q[i].x,q[i].y);
addtag(q[i].x,i,1);
addtag(q[i].y,i,1);
addtag(q[i].lca,i,-2);
q3[q[i].lca].push_back(MP(i,1));
}
solve1(0,1);
fr(i,1,n) if(top[i]==i) solve2(f[i],i);
minn=inf;
rsiz=n;
getroot(0,1);
solve(0,RT);
fr(i,1,m) writeln(q[i].ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 25ms
memory: 19844kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
3226 2028 4988 208 254 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1744 4981 12 1856 4825 4974 7274 19 82 4960 4680 208 7080 483 3693 808 1880 213 3394 1203 280 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 234 66 7074 525 4958 390 4713 2663 15 72...
result:
wrong answer 5th numbers differ - expected: '252', found: '254'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 1704ms
memory: 165884kb
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
1121 112292 5808 290183 156730 420 49301 361662 9704 19659 15297 231598 384 950 49 13188 143 52139 299229 103 57366 341730 135965 5836 1386 79 49306 82072 340074 194930 128425 363 1 10 6 3 3 18 65470 329357 329964 198948 331389 282453 73254 85513 333955 1214 320752 209176 5422 106 130701 154369 3332...
result:
wrong answer 1st numbers differ - expected: '757', found: '1121'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 1470ms
memory: 145584kb
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
78 138186 190250 5672 110415 267039 4095 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 288392 99 191654 102302 481 250486 188441 120515 292 199616 721 142 195166 2607 24301 135444 199768 2433 164666 180527 198261 15873 53672 83052 185790 141731 639 131 2130 188357 150164 ...
result:
wrong answer 2nd numbers differ - expected: '107329', found: '138186'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%