QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90582#5020. 举办乘凉州喵,举办乘凉州谢谢喵OtoriEmu0 1182ms98008kbC++144.7kb2023-03-23 20:05:322023-03-23 20:05:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-23 20:05:33]
  • 评测
  • 测评结果:0
  • 用时:1182ms
  • 内存:98008kb
  • [2023-03-23 20:05:32]
  • 提交

answer

/*
¤ï¤ó¤ï¤ó¡­¡­¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(int x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
Poly G[200005];
int fa[19][200005];
#define F(u) fa[0][u]
int dep[200005],son[200005],siz[200005],h[200005];
void dfs1(int u,int f)
{
	F(u)=f;
	dep[u]=dep[f]+1;
	siz[u]=1;
	for(int v:G[u])
	{
		if(v==f)	continue;
		dfs1(v,u),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])	son[u]=v;
		h[u]=max(h[u],h[v]+1);
	}
}
int top[200005];
void dfs2(int u,int t)
{
	top[u]=t;
	if(son[u])	dfs2(son[u],t);
	for(int v:G[u])	if((v^F(u)) && (v^son[u]))	dfs2(v,v);
}
int n,q;
int ans[200005];
inline int lowbit(int x){return x&(-x);}
namespace subt1
{
	int mx[200005],rt,s,sz[200005];
	PolyP qry[200005];
	bool del[200005];
	void getrt(int u,int f)
	{
		siz[u]=1,mx[u]=0;
		for(int v:G[u])
		{
			if(v==f || del[v])	continue;
			getrt(v,u);
			siz[u]+=siz[v];
			mx[u]=max(mx[u],sz[v]);
		}
		mx[u]=max(mx[u],s-siz[u]);
		if(mx[u]<mx[rt])	rt=u;
	}
	int dp[200005];
	int cnt[200005];
	Poly subt;
	int up;
	void dfs(int u,int f)
	{
		++cnt[dp[u]];
		up=max(up,dp[u]),subt.push_back(u);
		for(int v:G[u])
		{
			if(v==f || del[v])	continue;
			dp[v]=dp[u]+1;
			dfs(v,u);
		}
	}
	void solve(int u,int f,int coef)
	{
		subt.clear(),up=0;
		dfs(u,f);
		for(int i=1;i<=up;++i)	cnt[i]+=cnt[i-1];
		for(int p:subt)
		{
			for(P st:qry[p])
			{
				int d=st.first,id=st.second;
				if(d>=dp[p])	ans[id]+=coef*cnt[min(up,d-dp[p])];
			}
		}
		for(int i=0;i<=up;++i)	cnt[i]=0;
	}
	void solve(int u)
	{
		del[u]=true,dp[u]=0;
		solve(u,0,1);
		for(int v:G[u])	if(!del[v])	solve(v,u,-1);
		for(int v:G[u])
		{
			if(del[v])	continue;
			getrt(v,u);
			s=siz[v],rt=0;
			getrt(v,u);
			solve(rt);
		}
	}
	void solve()
	{
		mx[rt=0]=1e9;
		s=n,getrt(1,0);
		solve(rt);
	}
}
namespace subt2
{
	PolyP qry[200005];
	void add(int u,int v,int d,int id)
	{
		while(top[u]^top[v])
		{
			if(son[u])	qry[son[u]].emplace_back(d,-id);
			qry[top[u]].emplace_back(d,id);
			u=F(top[u]);
		}
		if(son[u])	qry[son[u]].emplace_back(d,-id);
		if(son[v])	qry[son[v]].emplace_back(d,id); // son of v -> u
	}
	int *f[200005],dp[400005],*now=dp;
	int tr[400005];
	const int N=4e5;
	int ver[400005],vc;
	void modify(int x,int w)
	{
		for(int i=x;i;i^=lowbit(i))
		{
			if(ver[i]^vc)	ver[i]=vc,tr[i]=0;
			tr[i]+=w;
		}
	}
	int query(int x)
	{
		int ans=0;
		for(int i=x;i<=N;i+=lowbit(i))
		{
			if(ver[i]^vc)	ver[i]=vc,tr[i]=0;
			ans+=tr[i];
		}
		return ans;
	}
	void dfs(int u)
	{
		f[u][0]=1;
		if(son[u])	f[son[u]]=f[u]+1,dfs(son[u]);
		for(int v:G[u])
		{
			if(v==F(u) || v==son[u])	continue;
			f[v]=now,now+=h[v]+1;
			dfs(v);
			for(int i=0;i<=h[v];++i)	f[u][i+1]+=f[u][i];
		}
		if(u==top[u])
		{
			#undef F
			vector<PolyP> E(h[u]+1),F(h[u]+1);
			int cnt=0;
			for(int x=u;x;x=son[x])
			{
				++cnt;
				for(P st:qry[x])
				{
					int d=st.first,id=st.second;
					if(d<=h[x])	E[d].emplace_back(cnt+d,id);
				}
				F[0].emplace_back(1,cnt);
				for(int y:G[x])
				{
					if(y==son[x] || y==fa[0][x])	continue;
					for(int i=0;i<=h[y];++i)	F[i+1].emplace_back(f[y][i],cnt+i+1);
				}
			}
			++vc;
			for(int i=0;i<=h[u];++i)
			{
				for(P st:F[i])	modify(st.second,st.first);
				for(P st:E[i])
				{
					int d=st.first,id=st.second;
					if(id<0)	ans[-id]-=query(d);
					else	ans[id]+=query(d);
				}
			}
		}
	}
	inline void solve(){f[1]=now,now+=h[1]+1,dfs(1);}
}
int LCA(int u,int v)
{
	if(dep[u]>dep[v])	swap(u,v);
	while(dep[u]<dep[v])	v=fa[__lg(dep[v]-dep[u])][v];
	if(u==v)	return u;
	for(int i=18;~i;--i)	if(fa[i][u]^fa[i][v])	u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}
int main(){
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	q=read();
	dfs1(1,0),dfs2(1,1);
	for(int i=1;i<=18;++i)	for(int j=1;j<=n;++j)	fa[i][j]=fa[i-1][fa[i-1][j]];
	for(int i=1;i<=q;++i)
	{
		int u=read(),v=read(),d=read();
		int p=LCA(u,v);
		subt1::qry[p].emplace_back(d,i);
		subt2::add(u,p,d,i),subt2::add(v,p,d,i);
	}
	subt1::solve(),subt2::solve();
	for(int i=1;i<=q;++i)	write(ans[i]),etr;
	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: 19372kb

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:

13082
3877
4988
208
252
17959
17286
3825
4974
2846
308
406
24967
312
4955
4988
4974
1963
4981
12
3713
4918
4974
4974
19
82
5257
8135
208
5166
498
6369
942
2955
213
13617
1727
279
84
4869
14072
70
81
28165
5257
742
12163
4974
113
526
75
163
209
4529
4981
19655
100
11799
232
66
4864
583
5254
390
22812...

result:

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

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 8
Accepted
time: 849ms
memory: 57144kb

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:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 381ms
memory: 55808kb

input:

199993
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: -8
Time Limit Exceeded

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1182ms
memory: 98008kb

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
1963372
5135952
8555
13713491
755865
8260
9786401
75
30734
149
58
704
309062316
25
377199306
489
400076098
4516964
22399
9329872
572536
99
326633472
239993
481
401133
450976
5018334
290
293395005
719
142
54837618
2996
87451
17544284
147787607
2711
112257565
114478542
383963537
35969
660404
945118...

result:

wrong answer 2nd numbers differ - expected: '107329', found: '1963372'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%