QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#295795#4901. Speike & Tomucup-team100420 496ms31836kbC++148.7kb2024-01-01 00:39:152024-01-01 00:39:16

Judging History

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

  • [2024-01-01 00:39:16]
  • 评测
  • 测评结果：20
  • 用时：496ms
  • 内存：31836kb
查看
  • [2024-01-01 00:39:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=1e5+10;
int n,m;
vector<int>to[N],tr[N];
namespace Tree{
	int dep[N],fa[N],siz[N],top[N],son[N];
	void dfs1(int u){
		dep[u]=dep[fa[u]]+1;
		for(int v:to[u])if(v^fa[u]){
			fa[v]=u,dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void dfs2(int u,int t){
		top[u]=t;
		if(son[u])dfs2(son[u],t);
		for(int v:to[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
	}
	int LCA(int u,int v){
		for(;top[u]^top[v];u=fa[top[u]]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
		}
		return dep[u]<dep[v]?u:v;
	}
	int sum[N];
	void link(int u,int v){
		if(dep[u]<dep[v])swap(u,v);
		if(fa[u]==v)return;
		if(fa[fa[u]]==v||fa[u]==fa[v]){
			tr[u].push_back(v),tr[v].push_back(u);
		}else{
			int t=LCA(u,v);
			sum[u]++,sum[t]--;
			sum[v]++,sum[fa[t]]--;
		}
	}
	void init(){
		dfs1(1),dfs2(1,1);
	}
	void push1(int u=1){
		for(int v:to[u])if(v^fa[u]){
			push1(v);
			sum[u]+=sum[v];
		}
	}
	int tot[N];
	void push2(int u=1){
		tot[u]=!!sum[u];
		for(int v:to[u])if(v^fa[u]){
			push2(v);
			tot[u]+=tot[v];
		}
	}
	int count(int u,int v){
		if(fa[u]==v)return tot[1]-tot[u];
		else if(fa[v]==u)return tot[v];
		else return 0;
	}
	bool count(int u){
		return !!sum[u];
	}
}
using Tree::count;
bool chk(int u,int v){
	return find(all(tr[u]),v)!=tr[u].end();
}
ll ans;
int rt,siz[N],mx[N],vis[N],dep[N],dis[N];
void dfs1(int u,int fa=0){
	siz[u]=1,mx[u]=0;
	for(int v:to[u])if(v^fa&&!vis[v]){
		dfs1(v,u);
		siz[u]+=siz[v];
		mx[u]=max(mx[u],siz[v]);
	}
}
void dfs2(int s,int u,int fa=0){
	mx[u]=max(mx[u],s-siz[u]);
	for(int v:to[u])if(v^fa&&!vis[v]){
		dfs2(s,v,u);
	}
	if(mx[u]<mx[rt])rt=u;
}
void dfs3(int u,int fa=0){
	dep[u]=dep[fa]+1;
	for(int v:to[u])if(v^fa){
		if(!vis[v])dfs3(v,u);
		else dep[v]=dep[u]+1;
	}
}
namespace Jump{
	const int K=__lg(N)+1;
	int tag[N],anc[K][N];
	vector<int>pos;
	void dfs(int u,int fa=0,int las=0){
		pos.push_back(u);
		anc[0][u]=fa;
		for(int v:tr[u])if(v==las)anc[0][u]=v;
		tag[u]=tag[anc[0][u]];
		if(fa!=rt&&anc[0][u]==rt)tag[u]=1;
		for(int v:to[u])if(v^fa){
			if(!vis[v])dfs(v,u,fa);
			else{
				pos.push_back(v),anc[0][v]=u;
				for(int w:tr[v])if(w==fa)anc[0][v]=w;
				tag[v]=tag[anc[0][v]];
				if(u!=rt&&anc[0][v]==rt)tag[v]=1;
			}
		}
	}
	void init(int u){
		pos.clear(),dfs(u);
		for(int i=1;(1<<i)<=n;i++){
			for(int u:pos)anc[i][u]=anc[i-1][anc[i-1][u]];
		}
		// debug(ary(anc[0],1,n));
	}
	int jump(int u,int t){
		int ans=0;
		for(int i=__lg(dep[u]-dep[t]+1);~i;i--){
			if(dep[anc[i][u]]>=dep[t])u=anc[i][u],ans+=1<<i;
		}
		return ans+(dep[u]>dep[t]);
	}
}
using Jump::jump;
void dfs4(int s,int u,int fa=0){
	dis[u]=jump(u,s),siz[u]=1;
	for(int v:to[u])if(v^fa){
		if(!vis[v]){
			dfs4(s,v,u);
			siz[u]+=siz[v];
		}else{
			dis[v]=jump(v,s);
		}
	}
}
struct BIT1{
	int c[N];
	vector<pair<int,int>>upd;
	void add(int x,int y){
		upd.push_back({x,-y});
		for(;x;x^=x&-x)c[x]+=y;
	}
	int get(int x,int y=0){
		for(;x<=n;x+=x&-x)y+=c[x];
		return y;
	}
	int count(){
		return upd.size();
	}
	void clr(int lim=0){
		for(int x,y;upd.size()>lim;upd.pop_back()){
			for(tie(x,y)=upd.back();x;x^=x&-x)c[x]+=y;
		}
	}
};
struct BIT2{
	int c[N];
	vector<pair<int,int>>upd;
	void add(int x,int y){
		upd.push_back({x,-y});
		for(;x<=n;x+=x&-x)c[x]+=y;
	}
	int get(int x,int y=0){
		for(;x;x^=x&-x)y+=c[x];
		return y;
	}
	int count(){
		return upd.size();
	}
	void clr(int lim=0){
		for(int x,y;upd.size()>lim;upd.pop_back()){
			for(tie(x,y)=upd.back();x<=n;x+=x&-x)c[x]+=y;
		}
	}
};
namespace Solve1{
	BIT1 A;
	void query(int u,int fa,int t=0,int p=0){
		if(count(fa,u))t=u,p=0;
		if(t){
			// debug(u,t,p,A.get(max(0,jump(u,t)-dep[t]+p+1)+1));
			ans+=A.get(max(0,jump(u,t)-dep[t]+p+1)+1);
		}
		for(int v:to[u])if(v^fa&&!vis[v]){
			int tt=t,pp=p;
			for(int w:tr[v]){
				if(dep[v]==dep[w]&&count(u,w))tt=v,pp=1;
			}
			query(v,u,tt,pp);
		}
	}
	void insert(int w,int u,int fa){
		A.add(dep[u]+1,w);
		for(int v:to[u])if(v^fa&&!vis[v]){
			insert(w,v,u);
		}
	}
	void solve(int u){
		A.add(dep[u]+1,1);
		for(int v:to[u])if(!vis[v])insert(1,v,u);
		for(int v:to[u])if(!vis[v]){
			insert(-1,v,u),query(v,u),insert(1,v,u);
		}
		A.clr();
	}
}
namespace Solve2{
	BIT2 A[2];
	void update(int t,int w,int u,int fa=0){
		A[t].add(dis[u]+1,w);
		for(int v:to[u])if(v^fa&&!vis[v]){
			update(t,w,v,u);
		}
	}
	void query(int u,int fa=0,int t=0,int d=0){
		if(t){
			// debug(u,t,d,dis[t],ans,d-dis[t]-1+1);
			ans+=A[0].get(max(0,d-dis[t]-1+1));
			ans+=A[1].get(max(0,d-dis[t]-Jump::tag[t]+1));
			// debug(ans);
		}
		int fi=0,se=0;
		for(int v:to[u])if(v^fa){
			if(count(u,v)){
				// debug("edge",u,v);
				if(!fi)fi=v;
				else if(!se)se=v;
				else if(dis[v]<dis[fi])fi=v;
				else if(dis[v]<dis[se])se=v;
			}
		}
		if(dis[se]<dis[fi])swap(fi,se);
		// debug(u,t,d);
		for(int v:to[u])if(v^fa&&!vis[v]){
			if(t)query(v,u,t,d+1);
			else if(fi&&v!=fi)query(v,u,fi,2);
			else if(se&&v!=se)query(v,u,se,2);
			else if(count(v,u))query(v,u,u,1);
			else query(v,u);
		}
	}
	int tag[N];
	void solve(int u){
		if(!count(u))A[0].add(dis[u]+1,1);
		for(int v:to[u])if(!vis[v])tag[v]=u;
		for(int v:to[u])if(!vis[v]&&!count(u,v)){
			update(0,1,v,u);
		}
		for(int v:to[u])if(!vis[v]&&!count(v,u)){
			int las=A[0].count();
			for(int w:tr[v])if(tag[w]==u){
				update(1,1,w,u),update(0,-1,w,u);
			}
			// debug(rt,v,ary(Tree::sum,1,n));
			query(v,u);
			A[0].clr(las),A[1].clr();
		}
		A[0].clr();
	}
}
namespace Solve3{
	BIT1 A[2];
	void update(int t,int w,int u,int fa=0){
		// if(!t)debug(t,u,w,dep[u]+1);
		A[t].add(dep[u]+1,w);
		for(int v:to[u])if(v^fa&&!vis[v]){
			update(t,w,v,u);
		}
	}
	void query(int o,int t,int p,int u,int fa=0){
		// if(u==11){
		// 	for(auto [x,y]:A[o].upd)debug("upd",x,-y);
		// }
		// debug(u,jump(u,t)+p+1,A[o].get(jump(u,t)+p+1));
		ans+=A[o].get(jump(u,t)+p+1);
		for(int v:to[u])if(v^fa&&!vis[v]){
			query(o,t,p,v,u);
		}
	}
	int tag[N];
	vector<int>o[N];
	void solve(int u){
		update(0,1,u),A[1].add(dep[u]+1,1);
		int cur=0,ret=Tree::tot[1];
		for(int v:to[u])if(!vis[v]){
			ret-=count(u,v);
			tag[v]=u;
			if(!count(u,v))update(1,1,v,u);
			else if(cur)cur=-1;
			else cur=v;
		}
		for(int v:to[u])if(!vis[v]&&!count(u,v)){
			int las=A[0].count(),pos=A[1].count();
			update(0,-1,v,u),update(1,-1,v,u);
			int fi=0,se=0;
			for(int w:tr[v]){
				if(count(u,w))(fi?se:fi)=w;
			}
			// debug(v,fi,se,tr[v]);
			if(fi&&se){
				query(0,v,1,v);
			}else if(fi){
				if(tag[fi]==u){
					o[fi].push_back(v);
				}else query(0,v,1,v);
			}else{
				// debug(u,count(u));
				// if(v==11)for(auto [x,y]:A[0].upd)debug("upd",x,-y);
				// debug("ok",cur);
				if(count(u))query(0,u,1,v);
				else if(!cur)query(0,u,1,v);
				else if(cur>0)debug(ret),query(!ret,u,1,v);
				else query(0,u,1,v);
			}
			// debug(v,ans);
			A[0].clr(las),A[1].clr(pos);
		}
		if(cur>0&&count(u))update(0,-1,cur,u);
		A[1].clr();
		for(int v:to[u])if(!vis[v]){
			if(o[v].empty())continue;
			int las=A[0].count();
			if(v^cur||count(u))update(0,-1,v,u);
			update(1,1,v,u);
			for(int w:o[v]){
				int las=A[0].count();
				update(0,-1,w,u);
				// debug("st",v,w,ans);
				query(0,w,1,w);
				// debug("mid",v,w,ans);
				if(v^cur||count(u))query(1,u,1,w);
				// debug("ed",v,w,ans);
				A[0].clr(las);
			}
			A[0].clr(las),A[1].clr();
			o[v].clear();
		}
		for(int v:to[u])if(!vis[v]){
			if(count(v,u)){
				// debug(u,v,siz[v]);
				ans+=siz[v];
			}
		}
		A[0].clr(),A[1].clr();
	}
}
void solve(int u){
	rt=0,dfs1(u),dfs2(siz[u],u),vis[u=rt]=1;
	dfs3(u),Jump::init(u),dfs4(u,u);
	Solve1::solve(u);
	Solve2::solve(u);
	Solve3::solve(u);
	// debug("root",u,ans);
	// if(u==4)exit(0);
	for(int v:to[u])if(!vis[v])solve(v);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		to[u].push_back(v),to[v].push_back(u);
	}
	Tree::init();
	for(int u,v;m--;){
		scanf("%d%d",&u,&v);
		Tree::link(u,v);
	}
	for(int i=1;i<=n;i++){
		sort(tr[i].begin(),tr[i].end());
	}
	Tree::push1();
	Tree::push2();
	// debug("sum",ary(Tree::sum,1,n));
	if(!Tree::tot[1])puts("0"),exit(0);
	mx[0]=n+1,dep[0]=-1,solve(1);
	cout<<ans<<endl;
	return 0;
}
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 10708kb

input:

20 3
1 2
1 3
3 4
4 5
1 6
6 7
1 8
5 9
8 10
5 11
7 12
11 13
12 14
11 15
4 16
7 17
2 18
1 19
3 20
8 20
12 4
10 1

output:

307

result:

ok 1 number(s): "307"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10812kb

input:

20 4
1 2
2 3
1 4
3 5
4 6
3 7
4 8
3 9
2 10
8 11
8 12
7 13
8 14
14 15
4 16
1 17
4 18
6 19
19 20
9 13
14 2
14 13
15 6

output:

343

result:

ok 1 number(s): "343"

Test #3:

score: 0
Accepted
time: 0ms
memory: 10712kb

input:

19 4
1 2
1 3
1 4
4 5
4 6
3 7
7 8
6 9
4 10
2 11
6 12
7 13
1 14
13 15
6 16
12 17
3 18
3 19
8 12
4 6
18 5
11 9

output:

314

result:

ok 1 number(s): "314"

Test #4:

score: 0
Accepted
time: 0ms
memory: 10812kb

input:

20 3
1 2
2 3
3 4
4 5
1 6
2 7
1 8
3 9
9 10
5 11
8 12
10 13
12 14
8 15
9 16
11 17
5 18
17 19
19 20
9 19
10 15
18 15

output:

358

result:

ok 1 number(s): "358"

Test #5:

score: 0
Accepted
time: 0ms
memory: 10712kb

input:

20 6
1 2
1 3
3 4
4 5
1 6
6 7
5 8
4 9
7 10
6 11
10 12
6 13
10 14
1 15
15 16
8 17
17 18
15 19
18 20
17 2
16 3
10 1
8 7
13 5
19 7

output:

361

result:

ok 1 number(s): "361"

Test #6:

score: 0
Accepted
time: 3ms
memory: 10920kb

input:

20 8
1 2
2 3
1 4
1 5
1 6
4 7
2 8
4 9
2 10
1 11
11 12
2 13
10 14
1 15
6 16
16 17
11 18
10 19
3 20
2 6
6 7
1 18
18 13
1 20
3 12
8 4
7 1

output:

324

result:

ok 1 number(s): "324"

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 10756kb

input:

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

output:

86690

result:

wrong answer 1st numbers differ - expected: '86687', found: '86690'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 10
Accepted

Test #29:

score: 10
Accepted
time: 36ms
memory: 16172kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #30:

score: 0
Accepted
time: 36ms
memory: 16068kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #31:

score: 0
Accepted
time: 288ms
memory: 25436kb

input:

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

output:

2254349415

result:

ok 1 number(s): "2254349415"

Test #32:

score: 0
Accepted
time: 496ms
memory: 31836kb

input:

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

output:

4706707961

result:

ok 1 number(s): "4706707961"

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-05 07:11:13 | 開源專案