QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185039#5020. 举办乘凉州喵,举办乘凉州谢谢喵zyz070 0ms0kbC++174.6kb2023-09-21 16:15:242023-09-21 16:15:25

Judging History

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

  • [2023-09-21 16:15:25]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-09-21 16:15:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=2e5+5;
int n,q,vis[N],siz[N],mxsiz[N];
vector<int> e[N];
struct Query{
	int u,v,k;
}qry[N];
int ans[N];
void get_root(int u,int fa,int tot,int& rt){
	siz[u]=1;
	mxsiz[u]=0;
	for(int v:e[u]){
		if(v!=fa&&!vis[v]){
			get_root(v,u,tot,rt);
			siz[u]+=siz[v];
			mxsiz[u]=max(mxsiz[u],siz[v]);
		}
	}
	mxsiz[u]=max(mxsiz[u],tot-siz[u]);
	if(!rt||mxsiz[u]<mxsiz[rt]){
		rt=u;
	}
}
int bel[N];
vector<int> deps[N],nxt_qs[N];
void fill(int u,int fa,int d,int rt){
	if(int(deps[rt].size())<=d){
		deps[rt].resize(d+1);
	}
	++deps[rt][d];
	bel[u]=rt;
	for(int v:e[u]){
		if(v!=fa&&!vis[v]){
			fill(v,u,d+1,rt);
		}
	}
}
namespace Solver{
	int fa[N],dep[N],son[N],hson[N],siz[N],mxdep[N];
	vector<int> poi;
	struct Query{
		int id,v,k;
	}qry[N*2];
	void dfs(int u){
		poi.push_back(u);
		dep[u]=dep[fa[u]]+1;
		siz[u]=1;
		for(int v:e[u]){
			if(v!=fa[u]&&!vis[v]){
				fa[v]=u;
				dfs(v);
				mxdep[u]=max(mxdep[u],mxdep[v]+1);
				siz[u]+=siz[v];
				if(mxdep[v]>=mxdep[son[u]]) son[u]=v;
				if(siz[v]>siz[hson[u]]) hson[u]=v;
			}
		}
	}
	int top[N],dfn[N],dfx,rk[N];
	void dfs2(int u,int tp){
		top[u]=tp;
		rk[dfn[u]=++dfx]=u;
		if(hson[u]) dfs2(hson[u],tp);
		for(int v:e[u]){
			if(v!=fa[u]&&v!=hson[u]&&!vis[v]){
				dfs2(v,v);
			}
		}
	}
	vector<tuple<int,int,int>> qs[N];
	vector<pair<int,int>> hldqs[N];
	int *f[N],buff[N*2],*cur;
	void dfs3(int u){
		if(son[u]) f[son[u]]=f[u]+1,dfs3(son[u]);
		for(int v:e[u]){
			if(v!=fa[u]&&v!=son[u]&&!vis[v]){
				f[v]=cur,cur+=mxdep[v]+1;
				dfs3(v);
				For(i,0,mxdep[v]) f[u][i+1]+=f[v][i];
			}
		}
		if(son[u]) f[u][0]=f[u][1]+1;
		else f[u][0]=1;
		for(auto [id,k,w]:qs[u]){
			ans[qry[id].id]+=w*(f[u][0]-(k<mxdep[u]?f[u][k+1]:0));
		}
	}
	void solve(int q,int rt){
		dfs(rt);
		dfs2(rt,rt);
		For(i,1,q){
			ans[qry[i].id]+=dep[qry[i].v]-1;
			if(!qry[i].k){
				++ans[qry[i].id];
				continue;
			}
			qs[qry[i].v].emplace_back(i,qry[i].k,1);
			for(int u=qry[i].v;u!=rt;u=top[u]){
				hldqs[fa[u]].emplace_back(i,1);
				qs[u].emplace_back(i,qry[i].k-1,-1);
				qs[hson[fa[u]]].emplace_back(i,qry[i].k-1,1);
				u=fa[u];
			}
		}
		vector<int> val;
		for(int i:poi){
			int cnt=0;
			for(int v:e[i]){
				if(v!=fa[i]&&!vis[v]){
					++cnt;
				}
			}
			if(!cnt){
				vector<int> pth;
				for(int u=i;u!=top[u];u=fa[u]){
					pth.push_back(u);
				}
				pth.push_back(top[i]);
				reverse(range(pth));
				val.clear();
				int ssiz=0;
				for(int u:pth){
					for(int v:e[u]){
						if(v!=fa[u]&&v!=hson[u]&&!vis[v]){
							val.resize(max<int>(val.size(),mxdep[v]+1));
							For(j,dfn[v],dfn[v]+siz[v]-1){
								int x=rk[j];
								++ssiz;
								val[dep[x]-dep[v]]+=siz[x];
							}
						}
					}
					for(auto [id,w]:hldqs[u]){
						int k=qry[id].k;
						ans[qry[id].id]+=w*(ssiz-(k<int(val.size())?val[k]:0));
					}
				}
			}
		}
		f[rt]=cur=buff;
		cur+=mxdep[rt]+1;
		dfs3(rt);
		For(i,0,2*int(poi.size())){
			buff[i]=0;
		}
		for(int u:poi){
			fa[u]=son[u]=hson[u]=mxdep[u]=0;
			qs[u].clear();
			hldqs[u].clear();
		}
		poi.clear();
		dfx=0;
	}
}
void solve(int u,const vector<int>& qs){
	int rt=0;
	get_root(u,0,siz[u],rt);
	u=rt;
	vis[u]=1;
	bel[u]=u;
	deps[u]={1};
	vector<int> vec;
	for(int v:e[u]){
		if(!vis[v]){
			fill(v,u,1,v);
			if(vec.size()<deps[v].size()){
				vec.resize(deps[v].size());
			}
			For(i,1,int(deps[v].size())-1){
				deps[v][i]+=deps[v][i-1];
			}
			For(i,0,int(deps[v].size())-1){
				vec[i]+=deps[v][i];
			}
		}
	}
	For(i,0,int(vec.size())-1){
		++vec[i];
	}
	int qcnt=0;
	for(int i:qs){
		auto [u,v,k]=qry[i];
		if(bel[u]!=bel[v]||(bel[u]==rt&&bel[v]==rt)){
			ans[i]-=vec[min(k,int(vec.size())-1)];
			Solver::qry[++qcnt]={i,u,k};
			Solver::qry[++qcnt]={i,v,k};
		}else{
			nxt_qs[bel[u]].push_back(i);
		}
	}
	Solver::solve(qcnt,u);
	deps[u].clear();
	for(int v:e[u]){
		if(!vis[v]){
			deps[v].clear();
		}
	}
	for(int v:e[u]){
		if(!vis[v]){
			solve(v,nxt_qs[v]);
		}
	}
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	For(i,1,n-1){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	siz[1]=n;
	vector<int> qs;
	cin>>q;
	For(i,1,q){
		cin>>qry[i].u>>qry[i].v>>qry[i].k;
		qs.push_back(i);
	}
	solve(1,qs);
	For(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

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
Runtime Error

Test #9:

score: 0
Runtime Error

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
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

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%