QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669542#5020. 举办乘凉州喵,举办乘凉州谢谢喵daduoli0 0ms0kbC++144.6kb2024-10-23 18:57:492024-10-23 18:57:49

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 18:57:49]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%