QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310721#5020. 举办乘凉州喵,举办乘凉州谢谢喵Harry271820 111ms26936kbC++144.3kb2024-01-21 17:09:592024-01-21 17:10:00

Judging History

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

  • [2024-01-21 17:10:00]
  • 评测
  • 测评结果:0
  • 用时:111ms
  • 内存:26936kb
  • [2024-01-21 17:09:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct edge{int v,nxt;}e[N<<1];
int cnt,h[N],f[N][20],dep[N],siz[N],son[N],dfn[N],id[N],top[N],n,m,u,v,k,tot,ans[N];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void dfs(int u,int fa)
{
	f[u][0]=fa;dep[u]=dep[fa]+1;siz[u]=1;
	for(int i=1;(1<<i)<=n;i++)f[u][i]=f[f[u][i-1]][i-1];
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;dfn[u]=++tot;id[tot]=u;
	if(son[u])dfs2(son[u],tp);
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==son[u]||v==f[u][0])continue;
		dfs2(v,v);
	}
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	for(int i=18;i>=0;i--)if(dep[f[u][i]]>=dep[v])u=f[u][i];
	if(u==v)return u;
	for(int i=18;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	return f[u][0];
}
struct node{int d,w,id;};
namespace Part1
{
	vector<node>qh[N],ql[N];int numl[N],numh[N],sum;
	void insert(int u,int v,int k,int id)
	{
		ans[id]+=dep[u]-dep[v]+1;
		if(son[u])qh[son[u]].emplace_back(node{min(dep[u]+k,n),1,id});
		ql[u].emplace_back(node{k,1,id});ql[f[v][0]].emplace_back(node{k,-1,id});
		while(top[u]!=top[v])
		{
			qh[top[u]].emplace_back(node{min(dep[f[top[u]][0]]+k,n),-1,id});
			qh[son[f[top[u]][0]]].emplace_back(node{min(dep[f[top[u]][0]]+k,n),1,id});
			u=f[top[u]][0];
		}
	}
	void dfs(int u,int fa)
	{
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa||v==son[u])continue;
			for(int j=dfn[v];j<dfn[v]+siz[v];j++)
			{
				int x=id[j];
				numl[dep[x]-dep[u]]+=siz[x];sum++; 
			}
		}
		for(int i=0;i<ql[u].size();i++)ans[ql[u][i].id]+=ql[u][i].w*(sum-numl[ql[u][i].d+1]);
		for(int i=0;i<qh[u].size();i++)ans[qh[u][i].id]+=qh[u][i].w*numh[qh[u][i].d+1];
		numh[dep[u]]+=siz[u];
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa)continue;
			dfs(v,u);
		}
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa||v==son[u])continue;
			for(int j=dfn[v];j<dfn[v]+siz[v];j++)
			{
				int x=id[j];
				numl[dep[x]-dep[u]]-=siz[x];sum--; 
			}
		}
		for(int i=0;i<qh[u].size();i++)ans[qh[u][i].id]+=qh[u][i].w*(siz[u]-numh[qh[u][i].d+1]);
	}
	void main()
	{
		dfs(1,0);
	}
}
namespace Part2
{
	int siz[N],mx[N],vis[N],S,rt,val[N],mxd,sum[N];vector<pair<int,int> >q[N];
	void find(int u,int fa)
	{
		siz[u]=1;mx[u]=0;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa||vis[v])continue;
			find(v,u);mx[u]=max(mx[u],siz[v]);
			siz[u]+=siz[v];
		}
		mx[u]=max(mx[u],S-siz[u]);
		if(mx[u]<mx[rt])rt=u;
	}
	int get(int u,int fa)
	{
		int res=1;
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa||vis[v])continue;
			res+=get(v,u);
		}
		return res;
	}
	void dfs(int u,int fa,int w,int d)
	{
		val[d]+=w;mxd=max(mxd,d);
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa||vis[v])continue;
			dfs(v,u,w,d+1);
		}
	}
	void dfs2(int u,int fa,int d)
	{
		for(int i=0;i<q[u].size();i++)if(q[u][i].first>=d)ans[q[u][i].second]+=sum[min(mxd,q[u][i].first-d)];
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(v==fa)continue;
			dfs2(v,u,d+1);
		}
	}
	void solve(int u)
	{
		vis[u]=1;mxd=0;
		dfs(u,0,1,0);
		for(int i=0;i<=mxd;i++)sum[i]=val[i];
		for(int i=1;i<=mxd;i++)sum[i]+=sum[i-1];
		for(int i=0;i<q[u].size();i++)ans[q[u][i].second]+=sum[q[u][i].first];
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(vis[v])continue;
			dfs(v,u,-1,1);
			for(int j=0;j<=mxd;j++)sum[j]=val[j];
			for(int j=1;j<=mxd;j++)sum[j]+=sum[j-1];
			dfs2(v,u,1);dfs(v,u,1,1);
		}
		dfs(u,0,-1,0);
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(vis[v])continue;
			mx[rt=0]=0x3f3f3f3f;S=get(v,u);find(v,u);solve(rt);
		}
	}
	void main()
	{
		mx[rt=0]=0x3f3f3f3f;S=n;find(1,0);solve(rt);
	}
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	cin>>u>>v;
    	add(u,v);add(v,u); 
	}
	dfs(1,0);dfs2(1,1);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>k;
		int Lca=lca(u,v);
		Part1::insert(u,Lca,k,i);Part1::insert(v,Lca,k,i);
		Part1::qh[Lca].emplace_back(node{min(dep[Lca]+k,n),-2,i});
		Part2::q[Lca].emplace_back(make_pair(k,i));
	}
	Part1::main();Part2::main();
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 111ms
memory: 26936kb

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:

7102
3040
15997
216
257
9840
9756
3025
15945
4301
316
467
14001
320
15823
15997
15945
2952
15990
12
2868
15010
15945
14556
19
82
15829
13913
216
15393
549
9563
1150
2892
221
7270
1545
339
84
15007
7210
70
81
12277
15829
744
15051
15945
113
566
75
171
217
3171
15990
10013
100
7044
237
66
15387
601
15...

result:

wrong answer 1st numbers differ - expected: '3226', found: '7102'

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

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%