QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108408#5020. 举办乘凉州喵,举办乘凉州谢谢喵fzj20070 1657ms302856kbC++175.6kb2023-05-24 22:14:372023-05-24 22:14:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-24 22:14:38]
  • 评测
  • 测评结果:0
  • 用时:1657ms
  • 内存:302856kb
  • [2023-05-24 22:14:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x){
	x=0;
	char ch=getchar();
	bool flag=0;
	while(ch>'9'||ch<'0') flag=flag||ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
	read(x),read(args...);
}
template<typename T>inline void prt(T x){
	if(x>9) prt(x/10);
	putchar(x%10+'0');
}
template<typename T>inline void put(T x){
	if(x<0) putchar('-'),x=-x;
	prt(x);
}
template<typename T>inline void put(char ch,T x){
	put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
	put(ch,x),put(ch,args...);
}
#define N 200005
int n,q,ans[N]; 
int head[N],cnt;
struct edge{
	int v,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
namespace Devide{
	vector<pair<int,int> >ques[N];
	bool vis[N];
	inline int get_siz(int x,int fa){
		if(vis[x]) return 0;
		int siz=1;
		for(int i=head[x];i;i=e[i].nxt)
			if(e[i].v!=fa) siz+=get_siz(e[i].v,x);
		return siz;
	}
	inline int get_wc(int x,int fa,int sum,int &wc){
		if(vis[x]) return 0;
		int siz=1,ms=0;
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v,t;
			if(v==fa) continue;
			t=get_wc(v,x,sum,wc),ms=max(ms,t),siz+=t;
		}
		ms=max(ms,sum-siz);
		if(ms<=sum/2) wc=x;
		return siz;
	}
	int t[N],maxlen,p[N],nowlen;
	inline void get_dist(int x,int fa,int dep,vector<pair<int,int> >& ins){
		if(vis[x]) return;
		nowlen=max(nowlen,dep),p[dep]++,ins.emplace_back(x,dep);
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v;
			if(v==fa) continue;
			get_dist(v,x,dep+1,ins);
		}
	}
	inline void devide(int x){
		if(vis[x]) return;
		get_wc(x,0,get_siz(x,0),x),vis[x]=1;
		maxlen=0,t[0]++;
		vector<pair<int,int> > all;
		all.emplace_back(x,0);
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v;
			if(vis[v]) continue;
			vector<pair<int,int> > ins;
			nowlen=0,get_dist(v,x,1,ins);
			for(int j=1;j<=nowlen;j++) p[j]+=p[j-1];
			for(auto val:ins){
				int u=val.first,d=val.second;
				for(auto tmp:ques[u])
					if(tmp.first>=d) ans[tmp.second]-=p[tmp.first-d];
				all.emplace_back(val);
			}
			for(int j=nowlen;j;j--) p[j]-=p[j-1];
			maxlen=max(maxlen,nowlen);
			for(int j=0;j<=nowlen;j++) t[j]+=p[j],p[j]=0;
		}
		for(int i=1;i<=maxlen;i++) t[i]+=t[i-1];
		for(auto val:all){
			int u=val.first,d=val.second;
			for(auto tmp:ques[u]) 
				if(tmp.first>=d) ans[tmp.second]+=t[tmp.first-d];
		}
		for(int i=0;i<=maxlen;i++) t[i]=0;
		for(int i=head[x];i;i=e[i].nxt) devide(e[i].v);
	}
	inline void solve(){
		memset(vis,0,sizeof(vis));
		memset(t,0,sizeof(t));
		devide(1);
	}
}
namespace Chain{
	int fa[N],dfn[N],dep[N],top[N],idx,son[N],siz[N];
	struct BIT{
		int c[N];
		BIT(){memset(c,0,sizeof(c));}
		#define lowbit(X) (X&-X)
		inline void update(int x,int v){
			for(;x<=n+1;x+=lowbit(x)) c[x]+=v;
		}
		inline int query(int x){
			int res=0;
			for(;x;x^=lowbit(x)) res+=c[x];
			return res;
		}
		inline int query(int l,int r){
			return query(r)-query(l-1);
		}
		#undef lowbit
	}B;
	inline void dfs1(int x,int fat){
		fa[x]=fat,dep[x]=dep[fat]+1,siz[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v;
			if(v==fat) continue;
			dfs1(v,x),siz[x]+=siz[v];
			if(siz[son[x]]<siz[v]) son[x]=v; 
		}
	}
	inline void dfs2(int x,int tf){
		top[x]=tf,dfn[x]=++idx;
		if(son[x]) dfs2(son[x],tf);
		for(int i=head[x];i;i=e[i].nxt)
			if(e[i].v!=son[x]&&e[i].v!=fa[x]) dfs2(e[i].v,e[i].v);
	}
	inline int lca(int x,int y){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]]) swap(x,y);
			x=fa[top[x]];
		}
		return x;
	}
	struct Ques{
		int l,r,id,val;
		Ques(){}
		Ques(int _l,int _r,int _id,int _val):l(_l),r(_r),id(_id),val(_val){}
	};
	vector<Ques> g1[N];
	vector<Ques> g2[N];
	inline void insert1(int x,int d,int id,int val){
		if(x<1||x>n||d<0) return;
		g1[dfn[x]-1].emplace_back(dep[x],min(dep[x]+d,n),id,-val);
		g1[dfn[x]+siz[x]-1].emplace_back(dep[x],min(dep[x]+d,n),id,val);
	}
	inline void insert2(int x,int d,int id,int val){
		if(x<1||x>n||d<0) return;
		g2[dfn[top[x]]-1].emplace_back(1,d+1,id,-val);
		g2[dfn[x]].emplace_back(1,d+1,id,val);
	}
	inline void insert(int x){
		int d=dep[x];
		while(x){
			g2[dfn[x]].emplace_back(d-dep[x]+1,0,0,1);
			x=fa[top[x]];
		}
	}
	inline void update(int x,int d,int id,int val){
		insert1(son[x],d-1,id,val);
		while(x){
			int p=top[x];
			insert1(p,d-1,id,-val);
//			insert1(son[fa[p]],d-1,id,val);
			insert2(x,d,id,val);
			x=fa[p];
		}
	}
	inline void prework(){
		memset(fa,0,sizeof(fa));
		memset(dfn,0,sizeof(dfn));
		memset(dep,0,sizeof(dep));
		memset(top,0,sizeof(top));
		memset(son,0,sizeof(son));
		memset(siz,0,sizeof(siz));
		idx=0;
		dfs1(1,0),dfs2(1,1);
	}
	inline void solve(){
		B=BIT();
		for(int i=1;i<=n;i++) g1[dfn[i]].emplace_back(dep[i],0,0,1);
		for(int i=1;i<=n;i++){
			for(auto tmp:g1[i]){
				if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
				else B.update(tmp.l,tmp.val);
			}
		}
		B=BIT();
		for(int i=1;i<=n;i++) insert(i);
		for(int i=1;i<=n;i++){
			for(auto tmp:g2[i]){
				if(tmp.id) ans[tmp.id]+=tmp.val*B.query(tmp.l,tmp.r);
				else B.update(tmp.l,tmp.val);
			}
		}
	}
}
int main(){
	read(n);
	for(int i=1,u,v;i<n;i++) read(u,v),add(u,v),add(v,u);
	read(q),Chain::prework();
	for(int i=1,x,y,d;i<=q;i++){
		read(x,y,d);
		int z=Chain::lca(x,y);
		Devide::ques[z].emplace_back(d,i);
		Chain::update(x,d,i,1);
		Chain::update(y,d,i,1);
		Chain::update(z,d,i,-2);
	}
	Devide::solve();
	Chain::solve();
	for(int i=1;i<=q;i++) put('\n',ans[i]);
	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: 22ms
memory: 28892kb

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:

1003
1820
4940
174
159
3804
3847
1347
2291
-124
232
26
2660
222
-11
-1812
4905
726
1401
12
828
-796
3923
552
19
63
4939
-835
144
3796
344
-442
-98
468
124
960
566
254
60
-754
2020
48
66
1666
2645
433
4708
2448
105
54
50
109
108
1869
3804
3478
75
1113
127
42
2749
207
4785
333
1420
1553
15
2554
59
-15...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1657ms
memory: 302856kb

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
69086
2307
174594
87618
182
31912
174485
6313
15724
11640
115209
219
689
9
9389
16
36017
175381
46
44726
177340
89680
3334
949
68
33944
59516
175163
188090
75088
127
1
3
3
2
3
9
61157
171749
193983
155706
196287
192862
53145
51862
172051
347
196282
199989
3543
12
99007
134461
191404
20166
7420
1...

result:

wrong answer 2nd numbers differ - expected: '69428', found: '69086'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1518ms
memory: 250120kb

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:

41
96024
22772
3972
55242
172160
3200
64091
58
6709
101
48
463
159809
25
176960
193
231412
29969
1698
26548
164439
60
156151
46623
117
182772
146770
7276
258
179241
631
75
-459
1976
14692
7811
-23026
1324
96068
-15290
197691
9622
-2324
69502
157074
106015
423
62
1097
231666
153799
7884
157917
126566...

result:

wrong answer 1st numbers differ - expected: '78', found: '41'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%