QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689881#4901. Speike & TomAcoipp0 23ms41304kbC++1410.0kb2024-10-30 19:02:182024-10-30 19:02:19

Judging History

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

  • [2024-10-30 19:02:19]
  • 评测
  • 测评结果：0
  • 用时：23ms
  • 内存：41304kb
查看
  • [2024-10-30 19:02:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ll int
#define N 100005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0,w = 1;
	char c = nc();
	while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res*w;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(long long x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
vector<ll> extra[N];
ll NOW,n,m,i,x,y,la[N],ne[N<<1],to[N<<1],et,vis[N],st[N][21],dep[N],key[N],keyboard[N],col[N],tim,si[N],st_cut[N][21],st_extra[N][21],depp[N],next_root,fath[N],dis0[N],dis1[N],type[N],DIS[N],FATH[N],instack[N];
vector<ll> v1,v2;
map<ll,ll> m1[N],m2[N];
long long ans;
struct BIT{
	ll tr[N];
	inline void add(ll k,ll x){while(k<=n) tr[k]+=x,k+=k&(-k);}
	inline ll query(ll k){
		ll num = 0;
		while(k) num+=tr[k],k-=k&(-k);
		return num;
	}
	inline void clear(ll k){while(k<=n) tr[k]=0,k+=k&(-k);}
}tr1,tr2;
inline void merge(ll x,ll y){
	et++,ne[et]=la[x],la[x]=et,to[et]=y;
	et++,ne[et]=la[y],la[y]=et,to[et]=x;
}
inline void dfs(ll x,ll fa){
	FATH[x] = fa;
	for(ll i=1;i<=17;i++) st[x][i]=st[st[x][i-1]][i-1];
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		dep[to[i]] = dep[x]+1,st[to[i]][0] = x;
		dfs(to[i],x);
	}
}
inline void dfs2(ll x,ll fa){
	keyboard[x] = vis[x];
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		dfs2(to[i],x);
		keyboard[x] += keyboard[to[i]];
	}
}
inline ll dis11(ll x,ll y){
	ll ans = dep[x]+dep[y];
	if(dep[x]>dep[y]) swap(x,y);
	for(ll i=17;i>=0;i--) if(dep[st[y][i]]>=dep[x]) y=st[y][i];
	if(x==y) return ans-2*dep[x];
	for(ll i=17;i>=0;i--) if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
	return ans-2*dep[st[x][0]];
}
inline void find_root(ll x,ll fa,ll &pos,ll &num,ll alls){
	ll now = 0;
	si[x] = 1;
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		find_root(to[i],x,pos,num,alls);
		si[x] += si[to[i]],now = max(now,si[to[i]]);
	}
	now = max(now,alls-si[x]);
	if(now<num) num=now,pos=x;
}
inline void init(ll x,ll fa,ll root){
	NOW = max(NOW,depp[x]);
	if(fa==-1) key[x]=keyboard[1];
	else{
		key[x]=keyboard[1];
		if(fa==FATH[x]) key[x]=keyboard[x];
		else key[x]-=keyboard[fa];
	}
	if(col[x]!=col[root]){
		si[x]=0,fath[x]=fa,dis0[x]=dis1[x]=0x3f3f3f3f;
		return ;
	}
	si[x] = (col[x]==col[root]),fath[x] = fa,dis0[x] = 0x3f3f3f3f,dis1[x] = 0x3f3f3f3f;
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa) continue;
		depp[to[i]] = depp[x] + 1; 
		init(to[i],x,root);
		si[x] += si[to[i]];
	}
}
inline void dfs_col(ll x,ll fa){
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		dfs_col(to[i],x);
	}
	col[x]=tim;
}
inline void dfs_insert_b(ll x,ll fa,ll delta){
	tr1.add(depp[x],delta);
	for(ll i=la[x];i;i=ne[i]) if(col[to[i]]==col[x]&&to[i]!=fa) dfs_insert_b(to[i],x,delta);
}
inline ll foundd(ll x,ll deppp){
	ll ans = 0;
	for(ll i=NOW;i>=0;i--) if(st_extra[x][i]&&depp[st_extra[x][i]]>deppp) x=st_extra[x][i],ans+=(1ll<<i);
	return ans+(depp[x]>deppp);
}
inline void dfs_find_a(ll x,ll fa,ll root){
	instack[x]=1;
	if(depp[x]==1) st_extra[x][0]=fa;
	else{
		st_extra[x][0]=fa;
		for(ll i=0;i<extra[x].size();i++) if(depp[extra[x][i]]==depp[x]-2) st_extra[x][0]=extra[x][i];
	}
	for(ll i=1;i<=NOW;i++) st_cut[x][i]=st_cut[st_cut[x][i-1]][i-1];
	for(ll i=1;i<=NOW;i++) st_extra[x][i]=st_extra[st_extra[x][i-1]][i-1];
	if(key[x]) ans+=tr1.query(n)+1;
	else{
		vector<ll> v(0);
		ll pos = x,step = -1,delta = -1;
		for(ll i=NOW;i>=0;i--) if(st_cut[pos][i]&&!key[st_cut[pos][i]]) pos=st_cut[pos][i];
		for(ll i=0;i<extra[pos].size();i++) if(depp[extra[pos][i]]==depp[pos]&&key[extra[pos][i]]) v.push_back(extra[pos][i]);
		if(v.size()) step=foundd(x,depp[pos])+1,delta=depp[v[0]];
		else step=foundd(x,depp[st_cut[pos][0]]),delta=depp[st_cut[pos][0]];
		pos=st_cut[pos][0];
		ll temp = 0;
		if(step-delta<0) ans++,temp=1;
		ans+=tr1.query(n)-tr1.query(max(0,step-delta));
		if(pos==root&&v.size()==1&&col[v[0]]==col[x]){
			next_root = v[0];
			v1.push_back(step),v2.push_back(foundd(x,depp[pos]));
		}
	}
	for(ll i=la[x];i;i=ne[i]){
		if(col[to[i]]!=col[x]||to[i]==fa) continue;
		st_cut[to[i]][0] = x;
		dfs_find_a(to[i],x,root);
	}
	for(ll i=0;i<=NOW;i++) st_cut[x][i]=0,st_extra[x][i]=0;
	instack[x]=0;
}
inline void dfss(ll x,ll fa,ll type){
	if(type==0) ans -= tr2.query(depp[x]);
	else ans += tr2.query(depp[x]-1);
	for(ll i=la[x];i;i=ne[i]) if(col[to[i]]==col[x]&&to[i]!=fa) dfss(to[i],x,type);
}
inline void dfs_find_b(ll x,ll fa,ll root){
	instack[x] = 1;
	for(ll i=1;i<=NOW;i++) st_cut[x][i]=st_cut[st_cut[x][i-1]][i-1];
	if(fa!=root) dis0[x] = 0x3f3f3f3f,dis1[x] = 0x3f3f3f3f;
	dis0[x] = min(dis0[x],dis0[fa]+1),dis1[x] = min(dis1[x],dis1[fa]+1);
	for(ll i=0;i<extra[x].size();i++){
		if(depp[extra[x][i]]==depp[x]-2){
			dis0[x] = min(dis0[x],dis0[extra[x][i]]+1);
			dis1[x] = min(dis1[x],dis1[extra[x][i]]+1);
		}
	}
	ll pos = x;
	for(ll i=NOW;i>=0;i--) if(st_cut[pos][i]&&key[root]-key[st_cut[pos][i]]) pos=st_cut[pos][i];
	if(st_cut[pos][0]&&(key[root]-key[pos])) pos=st_cut[pos][0];
	ll cntt = key[root];
	for(ll i=la[pos];i;i=ne[i]) if(instack[to[i]]&&depp[to[i]]>depp[pos]) cntt -= key[to[i]];
	if(cntt){
		ll temp = 0;
		for(ll i=0;i<extra[fath[pos]].size();i++) if(depp[extra[fath[pos]][i]]==depp[pos]+1&&!instack[extra[fath[pos]][i]]&&m1[extra[fath[pos]][i]][pos]) temp=1;
		if(fath[pos]!=root){
			ll step = -1,dis00 = -1,dis11 = -1;
			if(temp==0) step=depp[x]-depp[pos],dis00 = dis0[pos],dis11 = dis1[pos];
			else step=depp[x]-depp[pos]+1,dis00 = dis0[fath[pos]]+1,dis11 = dis1[fath[pos]]+1;
			if(step-1-dis00>=0) ans++;
			ans+=tr1.query(max(step-1-dis00,0));
			ans+=tr2.query(max(step-1-dis11,0));
		}
		else{
			ll step = -1,dis00 = -1,dis11 = -1;
			if(temp==0) step=depp[x]-depp[pos],dis00 = dis0[pos],dis11 = dis1[pos];
			else step=depp[x]-depp[pos]+1,dis00 = 1,dis11 = 1;
			if(step-1-dis00>=0) ans++;
			ans+=tr1.query(max(step-1-dis00,0));
			ans+=tr2.query(max(step-1-dis11,0));
		}
	}	
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		st_cut[to[i]][0] = x;
		dfs_find_b(to[i],x,root);
	}
	for(ll i=0;i<=NOW;i++) st_cut[x][i]=0;
	instack[x] = 0;
}
inline void dfs_insert_a(ll x,ll fa){
	if(type[x]==0) tr1.add(DIS[x],1);
	if(type[x]==1) tr2.add(DIS[x],1);
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		if(m2[to[i]][fa]) DIS[to[i]]=DIS[fa]+1,type[to[i]]=type[fa];
		else DIS[to[i]]=DIS[x]+1,type[to[i]]=type[x];
		dfs_insert_a(to[i],x);
	}
}
inline void dfs_erase_a(ll x,ll fa){
	if(type[x]==0) tr1.add(DIS[x],-1);
	if(type[x]==1) tr2.add(DIS[x],-1);
	for(ll i=la[x];i;i=ne[i]){
		if(to[i]==fa||col[to[i]]!=col[x]) continue;
		dfs_erase_a(to[i],x);
	}
}
inline void dfs_alls(ll x,ll fa,ll &alls){
	alls++;
	for(ll i=la[x];i;i=ne[i]) if(col[to[i]]==col[x]&&to[i]!=fa) dfs_alls(to[i],x,alls);
}
inline void solve(ll x){
	ll pos = -1,num = LLONG_MAX,cnt_key_son = 0,alls = 0;
	dfs_alls(x,-1,alls);
	if(alls==1) return ;	
	find_root(x,-1,pos,num,alls);
	NOW = 0;
	depp[pos] = 0,init(pos,-1,pos);
	NOW = log2(NOW);
	for(ll i=la[pos];i;i=ne[i]){
		ll keys = 0;
		if(FATH[pos]==to[i]) keys=keyboard[1]-keyboard[pos];
		else keys=keyboard[to[i]];
		if(keys) cnt_key_son++;
	}
	for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) dfs_insert_b(to[i],pos,1);
	if(!(cnt_key_son==1&&!vis[pos])){
		//在 A-P 上 
		ans += (alls-1); //Pos 作为 A 点 
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				next_root = -1;
				st_cut[to[i]][0] = pos;
				dfs_insert_b(to[i],pos,-1);
				dfs_find_a(to[i],pos,pos);
				if(next_root!=-1){
					for(ll j=0;j<v1.size();j++) tr2.add(v1[j],1);
					dfss(next_root,pos,0);
					for(ll j=0;j<v1.size();j++) tr2.clear(v1[j]);
					for(ll j=0;j<v2.size();j++) tr2.add(v2[j],1);
					dfss(next_root,pos,1);
					for(ll j=0;j<v2.size();j++) tr2.clear(v2[j]);
					v1.clear(),v2.clear();
				}
				dfs_insert_b(to[i],pos,1);
			}
		}
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) dfs_insert_b(to[i],pos,-1);
	}
	else{
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]&&key[to[i]]) dfs_insert_b(to[i],pos,-1);
		//在 B-P（不包含） 上 
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				st_cut[to[i]][0] = pos;
				if(!key[to[i]]) dfs_insert_b(to[i],pos,-1);
				dfs_find_a(to[i],pos,pos);
				v1.clear(),v2.clear();
				if(!key[to[i]]) dfs_insert_b(to[i],pos,1);
			}
		}
		ll root = -1;
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]&&!key[to[i]]) dfs_insert_b(to[i],pos,-1);
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(key[to[i]]) root=to[i];
		ll num = 0;
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(!key[to[i]]) ans+=si[to[i]],num+=si[to[i]];
		type[pos]=0,DIS[pos]=0;
		for(ll i=la[pos];i;i=ne[i]){
			if(col[to[i]]==col[pos]){
				if(!key[to[i]]){
					if(m2[to[i]][root]) DIS[to[i]]=1,type[to[i]]=1;
					else DIS[to[i]]=1,type[to[i]]=0;
					dfs_insert_a(to[i],pos);
				}
			} 
		}
		dis0[pos] = 0;
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(key[to[i]]) dis0[to[i]]=1,dis1[to[i]]=0,dfs_find_b(to[i],pos,pos);
		for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) if(!key[to[i]]) dfs_erase_a(to[i],pos);
	}
	for(ll i=la[pos];i;i=ne[i]) if(col[to[i]]==col[pos]) tim++,dfs_col(to[i],pos),solve(to[i]);
}
int main(){
	ll has = 0;
	n=read(),m=read();
	for(i=1;i<n;i++) x=read(),y=read(),merge(x,y),m1[x][y]=m1[y][x]=1;
	dep[1]=1,dfs(1,-1);
	for(i=1;i<=m;i++){
		x=read(),y=read();
		ll temp = dis11(x,y);
		if(temp==1) continue;
		if(temp==2) extra[x].push_back(y),extra[y].push_back(x),m2[x][y]=m2[y][x]=1;
		if(temp>2) vis[x]=1,vis[y]=1,has=1;
	}
	if(!has){
		write(0);
		return fwrite(obuf,p3-obuf,1,stdout),0;
	}
	dfs2(1,-1);
	solve(1);
	write(ans);
	return fwrite(obuf,p3-obuf,1,stdout),0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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:

19

result:

wrong answer 1st numbers differ - expected: '307', found: '19'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #29:

score: 10
Accepted
time: 23ms
memory: 40704kb

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: 10
Accepted
time: 20ms
memory: 41040kb

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
Wrong Answer
time: 16ms
memory: 41304kb

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:

67764

result:

wrong answer 1st numbers differ - expected: '2254349415', found: '67764'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-04 09:49:26 | OpenSource Project