QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#669542 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | daduoli | 0 | 0ms | 0kb | C++14 | 4.6kb | 2024-10-23 18:57:49 | 2024-10-23 18:57:49 |
answer
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;
using namespace std;
const Yzl Lty=20120712;
const int MAXN=4e5+10;
int n,Q;
int ans[MAXN],Fa[MAXN],dep[MAXN],sz[MAXN],mn[MAXN];
int mdep[MAXN],cp[MAXN];
vector<int> e[MAXN];
struct ddl {
int x,y,d;
}a[MAXN];
void add(int f,int t) {
e[f].pb(t);
}
void dfs1(int u,int fa) {
Fa[u]=fa; dep[u]=dep[fa]+1; sz[u]=1; mdep[u]=1;
for(auto t:e[u]) if(t!=fa) {
dfs1(t,u);
if(mdep[t]+1>mdep[u]) {
mdep[u]=mdep[t]+1;
cp[u]=t;
}
sz[u]+=sz[t]; if(sz[t]>sz[mn[u]]) mn[u]=t;
}
}
int tp[MAXN],dfn[MAXN],out[MAXN],cnt,id[MAXN];
void dfs2(int u,int fa,int top) {
tp[u]=top; dfn[u]=++cnt; id[cnt]=u;
if(mn[u]) dfs2(mn[u],u,top);
for(auto t:e[u]) if(t!=fa&&t!=mn[u]) dfs2(t,u,t);
out[u]=cnt;
}
int LCA(int x,int y) {
while(tp[x]!=tp[y]) {
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
x=Fa[tp[x]];
} return (dep[x]<dep[y]?x:y);
}
struct ask {
int d,i,o;
};
vector<ask> q1[MAXN],q2[MAXN],q3[MAXN];//g,f,t
void jp(int x,int y,int i,int o,int d) {
int lt=0;
while(tp[x]!=tp[y]) {
q1[x].pb((ask){d,i,1});
if(mn[x]&&d) q2[id[dfn[x]+1]].pb((ask){d-1,i,1});
if(lt&&d) q2[lt].pb((ask){d-1,i,-1});
lt=tp[x]; x=Fa[tp[x]];
}
if(o) {
if(y!=tp[y]) q1[id[dfn[y]-1]].pb((ask){d,i,-1});
} else q1[id[dfn[y]]].pb((ask){d,i,-1});
q1[x].pb((ask){d,i,1});
if(o&&mn[x]&&d) {
q2[id[dfn[x]+1]].pb((ask){d-1,i,1});
}
if(lt&&d) q2[lt].pb((ask){d-1,i,-1});
}
const int inf=1e9;
int SZ[MAXN],mx[MAXN],rt;
bool vis[MAXN];
void get_rt(int u,int fa,int S) {
SZ[u]=1; mx[u]=0;
for(auto t:e[u]) if(t!=fa&&!vis[t]) {
get_rt(t,u,S); SZ[u]+=SZ[t]; mx[u]=max(mx[u],SZ[t]);
} mx[u]=max(mx[u],S-SZ[u]);
if(mx[u]<mx[rt]) rt=u;
}
int js[MAXN],md,gs[MAXN],od;
void DFS(int u,int de,int fa,int o) {
js[de]+=o; md=max(md,de);
for(auto t:e[u]) if(t!=fa&&!vis[t]) DFS(t,de+1,u,o);
}
void Que(int u,int fa,int d) {
for(auto t:q3[u]) {
if(t.d>=d) {
if(t.d-d<=md||md==od) ans[t.i]+=gs[min(od,t.d-d)]*t.o;
else ans[t.i]+=(gs[min(od,t.d-d)]+js[md])*t.o;
}
}
for(auto t:e[u]) if(t!=fa&&!vis[t]) Que(t,u,d+1);
}
void calc(int u) {
++js[0]; md=0;
for(auto t:e[u]) if(!vis[t]) DFS(t,1,u,1);
for(int i=1;i<=md;++i) js[i]+=js[i-1];
for(int i=0;i<=md;++i) {
gs[i]=js[i],js[i]=0;
}
for(auto t:q3[u]) {
ans[t.i]+=gs[min(md,t.d)]*t.o;
} od=md;
for(auto t:e[u]) if(!vis[t]) {
md=0; DFS(t,1,u,-1);
for(int j=1;j<=md;++j) js[j]+=js[j-1];
for(int j=1;j<=md;++j) gs[j]+=js[j];
Que(t,u,1);
for(int j=1;j<=md;++j) gs[j]-=js[j],js[j]=0;
}
for(int i=0;i<=od;++i) gs[i]=0;
md=0;
}
void solve(int u,int S) {
rt=0; mx[0]=inf; get_rt(u,0,S); vis[rt]=1; calc(rt);
for(auto t:e[rt]) if(!vis[t]) {
if(SZ[t]<=SZ[rt]) solve(t,SZ[t]);
else solve(t,S-SZ[rt]);
}
}
int *f[MAXN],*g[MAXN],df[MAXN<<1],*idf=df+1,dg[MAXN<<1],*idg=dg+1;
void Give(int u) {
f[u]=idf; idf+=mdep[u]+2;
g[u]=idg; idg+=mdep[u]+2;
}
void dfs(int u,int fa) {
f[u][0]+=sz[u];
if(cp[u]) {
f[cp[u]]=f[u]+1;
g[cp[u]]=g[u]+1;
dfs(cp[u],u);
}
for(auto t:e[u]) if(t!=fa&&t!=cp[u]) {
Give(t); dfs(t,u);
for(int j=0;j<=mdep[t];++j) f[u][j+1]+=f[t][j];
}
for(auto t:q2[u]) ans[t.i]+=(sz[u]-(t.d+1<=mdep[u]?f[u][t.d+1]:0))*t.o;
}
int lp;
void tfs(int u,int fa,int dd) {
++lp; js[dep[u]-dd]+=sz[u]; md=max(md,dep[u]-dd);
for(auto t:e[u]) if(t!=fa) tfs(t,u,dd);
}
void rdfs(int u,int fa) {
js[0]+=sz[u]; ++lp;
for(auto t:e[u]) if(t!=fa&&t!=mn[u]) tfs(t,u,dep[u]);
for(auto t:q1[u]) ans[t.i]+=(lp-js[t.d+1])*t.o;
if(mn[u]) rdfs(mn[u],u);
else {
for(int i=0;i<=md;++i) js[i]=0;
md=0; lp=0; return ;
}
for(auto t:e[u]) if(t!=fa&&t!=mn[u]) rdfs(t,u);
}
int main () {
freopen("future.in","r",stdin);
freopen("future.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;++i) {
int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u);
} dfs1(1,0); dfs2(1,0,1);
scanf("%d",&Q);
for(int i=1;i<=Q;++i) {
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
if(a[i].x==a[i].y) {
q3[a[i].x].pb((ask){a[i].d,i,1});
continue;
}
int lca=LCA(a[i].x,a[i].y);
if(dfn[a[i].x]>dfn[a[i].y]) swap(a[i].x,a[i].y);
if(a[i].x==lca) jp(a[i].y,lca,i,1,a[i].d);
else {
jp(a[i].x,lca,i,1,a[i].d);
jp(a[i].y,lca,i,0,a[i].d);
}
q3[lca].pb((ask){a[i].d,i,1}); q2[lca].pb((ask){a[i].d,i,-1});
} solve(1,n); Give(1); dfs(1,0); rdfs(1,0);
for(int i=1;i<=Q;++i) {
printf("%d\n",ans[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
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:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #9:
score: 0
Dangerous Syscalls
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Dangerous Syscalls
Test #25:
score: 0
Dangerous Syscalls
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%