能帮我看看我的代码的复杂度吗,悬1关
查看原帖
能帮我看看我的代码的复杂度吗,悬1关
1422661
_APIO_楼主2024/8/26 15:05
#include<bits/stdc++.h>
using namespace std;
/*找出以谁为根*/
vector<int>u[200010];
int f[200010];
int d[200010];
int v[200010];
int n,k;
int g;
int sum;
int ans;
int dfs1(int id,int fa){
	if(g){
		return 0;
	}
	int sum=0;
	for(auto i:u[id]){
		if(i!=fa){
			sum+=dfs1(i,id);
		}
	}
	d[id]=1;
	if(g){
		return 0;
	}
	++sum;
	if(sum>=k){
		int flag=0;
		for(int i=1;i<=k;i++){
			if(!d[v[i]]){
				flag=1;
				break;
			}
		}
		if(!flag){
			g=id;
		}
		//cout<<g<<endl;
    }
	return sum;
}
int dfs2(int id,int fa,int cnt){
	int sum=0;
	//cout<<id<<endl;
	if(f[id]){
		ans+=cnt;
		cnt--;
	}
	for(auto i:u[id]){
		if(i!=fa){
			sum+=dfs2(i,id,cnt+1);
		}
	}
	if(sum>=2 && !f[id]){
		ans-=sum-1;
	}
	if(f[id]){
		sum++;
	}
	return sum;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		u[a].push_back(b);
		u[b].push_back(a);
	}
	for(int i=1;i<=k;i++){
		cin>>v[i];
		f[v[i]]=1;
	}
	dfs1(1,0);
	
	//cout<<g;
	dfs2(g,0,1);
	cout<<ans;
}

我算的最劣复杂度是 O(nk−k2)O(nk-k^2),平均复杂度是 O(klog⁡2(n−k))O(k \log_2 (n-k) )。但是这份代码在赛时轻松过了。是我复杂度算错了还是数据太水了

2024/8/26 15:05
加载中...