QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310725#5020. 举办乘凉州喵,举办乘凉州谢谢喵Harry271820 703ms120184kbC++144.4kb2024-01-21 17:13:322024-01-21 17:13:36

Judging History

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

  • [2024-01-21 17:13:36]
  • 评测
  • 测评结果:0
  • 用时:703ms
  • 内存:120184kb
  • [2024-01-21 17:13:32]
  • 提交

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||vis[v])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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 16ms
memory: 27540kb

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
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
3585
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
35...

result:

wrong answer 24th numbers differ - expected: '4974', found: '3585'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 529ms
memory: 71940kb

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:

1193
104153
9170
249115
159552
221
35704
199179
7224
17078
30146
119050
560
777
23
11778
89
71317
213653
109
49747
193400
98540
5148
1471
68
66375
62281
199860
292121
93110
398
1
24
6
4
3
14
61421
199859
199152
259687
196278
260439
55552
56091
179198
931
196281
199988
5352
112
102787
142067
198158
2...

result:

wrong answer 1st numbers differ - expected: '757', found: '1193'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 703ms
memory: 120184kb

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
107329
190250
5672
110415
199160
3826
96672
75
13429
149
58
704
199639
25
190454
489
198350
197627
10273
172193
192719
99
191654
80328
481
195140
172164
120515
290
199616
719
142
195166
2607
20737
135444
199768
2433
164666
180527
198261
14511
53672
69060
185790
110874
639
131
2130
188357
150164
2...

result:

wrong answer 28th numbers differ - expected: '170809', found: '172164'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%