QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#702904#5020. 举办乘凉州喵,举办乘凉州谢谢喵FLY0 794ms180040kbC++145.7kb2024-11-02 16:46:372024-11-02 16:46:38

Judging History

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

  • [2024-11-02 16:46:38]
  • 评测
  • 测评结果:0
  • 用时:794ms
  • 内存:180040kb
  • [2024-11-02 16:46:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define gc getchar
#define pb push_back
#define abs_(x) max(x,-(x))
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define all(x) x.begin(),x.end()
const int N=2e5+5;
int read()
{
	int x=0; int y=1; char c=gc();
	for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return y?x:-x;
}
int n,Q;
vector<int> e[N];

int ans[N];

int fa[N],d[N],sz[N],son[N],dfn[N],idfn[N],ed[N],dct,top[N];
int bz[20][N],lg[N];
void dfs0(int u)
{
	d[u]=d[fa[u]]+1;
	sz[u]=1;
	son[u]=0;
	for(int v:e[u]) if(v^fa[u])
	{
		fa[v]=u;
		dfs0(v);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs1(int u,int tp)
{
	top[u]=tp;
	dfn[u]=++dct;
	idfn[dfn[u]]=u;
	bz[0][dct]=dfn[fa[u]];
	
	if(son[u]) dfs1(son[u],tp);
	for(int v:e[u]) if((v^fa[u])&&(v^son[u]))
	{
		dfs1(v,v);
	}
	ed[u]=dct;
}
int get_mn(int l,int r)
{
	int t=lg[r-l+1];
	return min(bz[t][l],bz[t][r-(1<<t)+1]);
}
int lca(int u,int v)
{
	if(u==v) return u;
	u=dfn[u],v=dfn[v];
	if(u>v) swap(u,v);
	return idfn[get_mn(u+1,v)];
}
int dis(int u,int v)
{
	return d[u]+d[v]-2*d[lca(u,v)]; 
}


int Fa[N],Sz[N],Rt,n2;
bool vs[N];
vector<int> d1[N],d2[N];
int tsz[N],mx[N];
void dfs2(vector<int> &x,int u,int fa,int s)
{
//	cout<<u<<" "; 
//	cout<<"          "<<s<<" "<<u<<endl;
//	cout<<u<<endl;
	x[dis(u,s)]++;
	for(int v:e[u]) if((v^fa)&&!vs[v]) dfs2(x,v,u,s);
}
int get_sz(int u,int fa)
{
//	cout<<u<<endl;
	int s=1;
	for(int v:e[u]) if((v^fa)&&!vs[v]) s+=get_sz(v,u);
	return s; 
}
void get_rt(int u,int fa)
{
//	cout<<u<<endl;
	tsz[u]=1; mx[u]=0;
	for(int v:e[u]) if((v^fa)&&!vs[v])
	{
		get_rt(v,u);
		tsz[u]+=tsz[v];
		tomax(mx[u],tsz[v]);
	}
	tomax(mx[u],n2-tsz[u]);
	if(mx[u]*2<=n2) Rt=u;
}
void Divide(int u)
{
//	cout<<u<<endl;
	vs[u]=1;
	d1[u].resize(Sz[u]+3,0);
	d2[u].resize(Sz[u]+3,0);
	dfs2(d1[u],u,0,u);
//	puts("");
	if(u^1) dfs2(d2[u],u,0,Fa[u]);
//	puts("");
	for(int i=1;i<d1[u].size();i++) d1[u][i]+=d1[u][i-1];
	for(int i=1;i<d2[u].size();i++) d2[u][i]+=d2[u][i-1];
//	for(int i=0;i<d1[u].size();i++) cout<<d2[u][i]<<" ";
//	puts("");
//	puts("");
	for(int v:e[u]) if(!vs[v])
	{
		n2=get_sz(v,u);
		get_rt(v,u);
		Fa[Rt]=u;
		Sz[Rt]=n2;
		Divide(Rt);
	}
}
int query1(int u,int d)
{
	int s=0;
	for(int v=u;v;v=Fa[v])
	{
		int t=dis(v,u);
		if(t<=d) 
		{
			int tt=(int)d1[v].size()-1;
			s+=d1[v][min(tt,d-t)];
//			cout<<u<<" "<<v<<" "<<d<<" "<<t<<"   "<<d1[v][d-t]<<","<<d2[v][d-t]<<endl;
			if(v!=1&&dis(u,Fa[v])<=d) s-=d2[v][min(tt,d-dis(u,Fa[v]))];
		}
	}
	return s;
}

void pre1()
{
	For(i,2,n) lg[i]=lg[i>>1]+1;
	dfs0(1);
	dfs1(1,1);
	For(i,1,lg[n])
	{
		For(j,1,n-(1<<i)+1) bz[i][j]=min(bz[i-1][j],bz[i-1][j+(1<<i-1)]);
	}
	Sz[1]=n;
	Divide(1);
//	For(i,1,n)
//	{
//		For(j,1,n) cout<<dis(i,j)<<" ";
//		puts("");
//	}
}




struct _N
{
	int id,d,x;
};
vector<_N> g1[N],g2[N];
void solve(int id,int u,int d,int x)
{
	g1[u].pb((_N){id,d,x});
	if(d)
	{
		g2[son[u]].pb((_N){id,d-1,x});
		for(int v=top[u];v^1;v=top[fa[v]])
		{
			g2[v].pb((_N){id,d-1,-x});
			g2[son[fa[v]]].pb((_N){id,d-1,x});
		}
	}
}
namespace B
{
	int c[N];
	void cls() { memset(c,0,sizeof(c)); }
	#define lb(x) x&-x
	void add(int x,int y)
	{
		x++;
		for(int i=x;i<=n+2;i+=lb(i)) c[i]+=y;
	}
	void cls(int x)
	{
		x++;
		for(int i=x;i<=n+2;i+=lb(i)) c[i]=0;
	}
	int get(int x)
	{
		x++;
		tomin(x,n+2);
		int s=0;
		for(int i=x;i;i-=lb(i)) s+=c[i];
		return s;
	} 
	int get(int l,int r) { return get(r)-get(l-1); }
	#undef lb
}
void dfs4(int u,int d,int x)
{
	B::add(d,x);
	for(int v:e[u]) if(v^fa[u]) dfs4(v,d+1,x);
}
void dfs3(int u)
{
	B::add(0,1);
	for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,1);
	for(auto t:g1[u])
	{
		int s=B::get(t.d)*t.x;
//		cout<<"           "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
		ans[t.id]+=s;
	}
	for(int v:e[u]) 
	{
		if((v^fa[u])) dfs3(v);
	}
	B::add(0,-1);
	for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,-1);
}
void dfs6(int u,int x)
{
	B::add(d[u],x);
	for(int v:e[u]) if(v^fa[u]) dfs6(v,x);
}
void dfs5(int u,bool cs)
{
	for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs5(v,1);
	if(son[u]) dfs5(son[u],0);
	B::add(d[u],1);
	for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs6(v,1);
	for(auto t:g2[u])
	{
		int s=B::get(d[u],d[u]+t.d)*t.x;
//		For(i,0,2) cout<<B::get(i)<<" "; puts("");
//		cout<<"   "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
		ans[t.id]+=s;
	}
	if(cs)
	{
		For(k,dfn[u],ed[u]) B::cls(d[idfn[k]]);
	}
}
void work1()
{
	dfs3(1);
	dfs5(1,1);
}
void Cls()
{
	For(u,1,n) e[u].clear();
	dct=0;
	memset(ans,0,Q+2<<2);
	For(u,1,n) d1[u].clear();
	For(u,1,n) d2[u].clear();
	memset(vs,0,n+2);
	
	For(u,1,n) g1[u].clear();
	For(u,1,n) g2[u].clear();
}


void work()
{
	n=read();
	For(i,1,n-1)
	{
		int u=read(),v=read();
		e[u].pb(v);
		e[v].pb(u);
	}
	pre1();
	Q=read();
	For(i,1,Q)
	{
		int u=read(),v=read(),d=read();
		int lc=lca(u,v);
//		cout<<lc<<endl;
		solve(i,u,d,1);
		solve(i,v,d,1);
		solve(i,lc,d,-2);
		ans[i]+=query1(lc,d);
//		cout<<"    "<<query1(u,d)<<" "<<query1(v,d)<<endl;
	}
	work1();
	For(i,1,Q) printf("%d\n",ans[i]);
	
	Cls();
}
signed main()
{
//	freopen("ex_color.in","r",stdin);
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
//	freopen("D.in","r",stdin);
//	freopen("D.out","w",stdout);
	int T=1;
	while(T--) work();
	return 0;
}


/*
5
1 2
1 3
2 4
2 5
5
1 2 0
1 2 1
1 2 2
1 2 3
4 3 1

*/


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 14ms
memory: 45884kb

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
4974
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
49...

result:

wrong answer 757th numbers differ - expected: '120', found: '121'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 794ms
memory: 180040kb

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:

wrong answer 1057th numbers differ - expected: '282', found: '283'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 771ms
memory: 156396kb

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
170809
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 5292nd numbers differ - expected: '371', found: '372'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%