QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61902#5020. 举办乘凉州喵,举办乘凉州谢谢喵AFewSuns0 1704ms165884kbC++145.8kb2022-11-15 21:20:192022-11-15 21:20:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-15 21:20:22]
  • 评测
  • 测评结果:0
  • 用时:1704ms
  • 内存:165884kb
  • [2022-11-15 21:20:19]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
namespace my_std{
	#define ll int
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 2e9
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define LC lc[x]
#define RC rc[x]
vector<pair<ll,ll> > q1[200020],q2[200020],q3[200020];
ll n,m,head[200020],cnt=0;
ll siz[200020],wson[200020],top[200020],f[200020],dep[200020];
ll rt[200020],tree[5000050],lc[5000050],rc[5000050],tot=0;
ll RT,rsiz,minn,tr[200020],num[200020];
bl ck[200020];
struct edge{
	ll nxt,to;
}e[400040];
struct node{
	ll x,y,lca,d,ans;
}q[200020];
void add(ll u,ll v){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
void dfs1(ll fa,ll u){
	f[u]=fa;
	dep[u]=dep[fa]+1;
	siz[u]=1;
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		dfs1(u,v);
		if(siz[v]>siz[wson[u]]) wson[u]=v;
		siz[u]+=siz[v];
	}
}
void dfs2(ll u,ll topp){
	top[u]=topp;
	if(wson[u]) dfs2(wson[u],topp);
	go(u){
		ll v=e[i].to;
		if(v==f[u]) continue;
		if(v!=wson[u]) dfs2(v,v);
	}
}
ll get_lca(ll x,ll y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
void addtag(ll x,ll id,ll v){
	if(!x) return;
	q[id].ans+=v*dep[x];
	if(wson[x]) q1[wson[x]].push_back(MP(id,v));
	while(x){
		q2[x].push_back(MP(id,v));
		if(f[top[x]]){
			q1[top[x]].push_back(MP(id,-v));
			q1[wson[f[top[x]]]].push_back(MP(id,v));
		}
		x=f[top[x]];
	}
}
void pushup(ll x){
	tree[x]=tree[LC]+tree[RC];
}
void mdf(ll &x,ll l,ll r,ll pos){
	if(!x) x=++tot;
	if(l==r){
		tree[x]++;
		return;
	}
	ll mid=(l+r)>>1;
	if(pos<=mid) mdf(LC,l,mid,pos);
	else mdf(RC,mid+1,r,pos);
	pushup(x);
}
ll query(ll x,ll l,ll r,ll ql,ll qr){
	if(!x||ql>qr) return 0;
	if(ql<=l&&r<=qr) return tree[x];
	ll mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=query(LC,l,mid,ql,qr);
	if(mid<qr) res+=query(RC,mid+1,r,ql,qr);
	return res;
}
ll merge(ll x,ll y,ll l,ll r){
	if(!x) return y;
	if(!y) return x;
	if(l==r){
		tree[x]+=tree[y];
		return x;
	}
	ll mid=(l+r)>>1;
	LC=merge(LC,lc[y],l,mid);
	RC=merge(RC,rc[y],mid+1,r);
	pushup(x);
	return x;
}
il ll lowbit(ll x){
	return x&(-x);
}
il void mdf(ll x,ll v){
	while(x<=n){
		tr[x]+=v;
		x+=lowbit(x);
	}
}
il ll query(ll x){
	ll res=0;
	while(x){
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
void solve1(ll fa,ll u){
	mdf(rt[u],1,n,dep[u]);
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		solve1(u,v);
		rt[u]=merge(rt[u],rt[v],1,n);
	}
	fr(i,0,(ll)q1[u].size()-1){
		ll id=q1[u][i].fir,v=q1[u][i].sec;
		if(!q[id].d) continue;
		q[id].ans+=v*query(rt[u],1,n,1,min(n,dep[u]+q[id].d-1));
	}
}
void dfs(ll fa,ll u,ll now,ll t){
	mdf(now,t);
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		dfs(u,v,now+1,t);
	}
}
void solve2(ll fa,ll u){
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		if(v!=wson[u]) dfs(u,v,1,1);
	}
	fr(i,0,(ll)q2[u].size()-1){
		ll id=q2[u][i].fir,v=q2[u][i].sec;
		q[id].ans+=v*query(min(n,q[id].d));
	}
	if(wson[u]) solve2(u,wson[u]);
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		if(v!=wson[u]) dfs(u,v,1,-1);
	}
}
void getroot(ll fa,ll u){
	siz[u]=1;
	ll maxx=0;
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		getroot(u,v);
		siz[u]+=siz[v];
		maxx=max(maxx,siz[v]);
	}
	maxx=max(maxx,rsiz-siz[u]);
	if(maxx<minn){
		minn=maxx;
		RT=u;
	}
}
void dfs3(ll fa,ll u){
	siz[u]=1;
	dep[u]=dep[fa]+1;
	num[dep[u]]++;
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		dfs3(u,v);
	}
}
void dfs4(ll r,ll fa,ll u,ll t){
	fr(i,0,(ll)q3[u].size()-1){
		ll id=q3[u][i].fir;
		if(q[id].d>=dep[u]) q[id].ans+=num[min(siz[r],q[id].d-dep[u])];
	}
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		dfs4(r,u,v,t);
	}
}
void solve(ll fa,ll u){
	ck[u]=1;
	dep[u]=0;
	num[0]++;
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		dfs3(u,v);
	}
	fr(i,1,siz[u]) num[i]+=num[i-1];
	dfs4(u,fa,u,1);
	fr(i,0,siz[u]) num[i]=0;
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		dfs3(u,v);
		fr(j,1,siz[v]) num[j]+=num[j-1];
		dfs4(v,u,v,-1);
		fr(j,0,siz[v]) num[j]=0;
	}
	go(u){
		ll v=e[i].to;
		if(v==fa||ck[v]) continue;
		minn=inf;
		rsiz=siz[v];
		getroot(u,v);
		solve(u,v);
	}
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("wa.out","w",stdout);
	n=read();
	fr(i,2,n){
		ll u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dfs1(0,1);
	dfs2(1,1);
	m=read();
	fr(i,1,m){
		q[i].x=read();
		q[i].y=read();
		q[i].d=read();
		q[i].lca=get_lca(q[i].x,q[i].y);
		addtag(q[i].x,i,1);
		addtag(q[i].y,i,1);
		addtag(q[i].lca,i,-2);
		q3[q[i].lca].push_back(MP(i,1));
	}
	solve1(0,1);
	fr(i,1,n) if(top[i]==i) solve2(f[i],i);
	minn=inf;
	rsiz=n;
	getroot(0,1);
	solve(0,RT);
	fr(i,1,m) writeln(q[i].ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 25ms
memory: 19844kb

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
254
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1744
4981
12
1856
4825
4974
7274
19
82
4960
4680
208
7080
483
3693
808
1880
213
3394
1203
280
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
234
66
7074
525
4958
390
4713
2663
15
72...

result:

wrong answer 5th numbers differ - expected: '252', found: '254'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1704ms
memory: 165884kb

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:

1121
112292
5808
290183
156730
420
49301
361662
9704
19659
15297
231598
384
950
49
13188
143
52139
299229
103
57366
341730
135965
5836
1386
79
49306
82072
340074
194930
128425
363
1
10
6
3
3
18
65470
329357
329964
198948
331389
282453
73254
85513
333955
1214
320752
209176
5422
106
130701
154369
3332...

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1470ms
memory: 145584kb

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
138186
190250
5672
110415
267039
4095
96672
75
13429
149
58
704
199639
25
190454
489
198350
197627
10273
172193
288392
99
191654
102302
481
250486
188441
120515
292
199616
721
142
195166
2607
24301
135444
199768
2433
164666
180527
198261
15873
53672
83052
185790
141731
639
131
2130
188357
150164
...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%