QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#702612#5020. 举办乘凉州喵,举办乘凉州谢谢喵FLY0 883ms180020kbC++145.4kb2024-11-02 16:16:582024-11-02 16:16:58

Judging History

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

  • [2024-11-02 16:16:58]
  • 评测
  • 测评结果:0
  • 用时:883ms
  • 内存:180020kb
  • [2024-11-02 16:16:58]
  • 提交

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) 
		{
			s+=d1[v][d-t];
//			cout<<u<<" "<<v<<" "<<d<<" "<<t<<"   "<<d1[v][d-t]<<","<<d2[v][d-t]<<endl;
			if(v!=1&&dis(v,Fa[v])<=d) s-=d2[v][d-dis(v,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;i+=lb(i)) c[i]+=y;
	}
	void cls(int x)
	{
		x++;
		for(int i=x;i<=n;i+=lb(i)) c[i]=0;
	}
	int get(int x)
	{
		x++;
		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;
//		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);
	int T=1;
	while(T--) work();
	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: 8ms
memory: 32064kb

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
1714
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
258
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
2577
15
49...

result:

wrong answer 18th numbers differ - expected: '1551', found: '1714'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 883ms
memory: 180020kb

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:

-8525
-55252
-28378
178011
81679
-1098
13497
199157
-110385
-117147
-96929
106609
-20219
-3518
-233
-109204
-208
-70887
145250
-92
-93956
192895
78055
-118502
152
68
-46235
-46212
199892
170799
56334
-446
1
3
2
3
3
-5
-41848
199899
199171
96354
196199
192866
-37364
-55003
143174
-34796
196172
199973...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 728ms
memory: 152732kb

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
3851
96672
75
13429
149
58
704
199639
25
190454
489
198350
197627
10273
172193
191787
99
191654
80328
481
195140
173240
120515
288
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 7th numbers differ - expected: '3826', found: '3851'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%