求助!树的重心!(没用前项链式星)
查看原帖
求助!树的重心!(没用前项链式星)
747305
LGCat_ERR楼主2024/12/29 14:51

目前的问题是size函数内求整棵树权值出了问题 (QAQ)

#include<bits/stdc++.h>
using namespace std;

bool g[1000];//找根节点 
struct e{
	int w,u,v;
}a[1000];
int size[10000];//子树总值 
int f[1000];//重心转移 
int num=0;
//int q[10000][1000];//队列(?) 

void dfs(int root,int tet){//问题所在
	size[root]=a[root].w;
	if(a[root].u!=0){
		dfs(a[root].u,tet++);
	}
	if(a[root].v!=0){
		dfs(a[root].v,tet++);	
	}

}


void ff(int root){
	f[a[root].u]=f[root]+size[num]-size[a[root].u]-size[a[root].u];
	if(a[root].u!=0){
//		cout<<a[root].u<<"->"<<f[a[root].u]<<endl;
		ff(a[root].u);
	}
	f[a[root].v]=f[root]+size[num]-size[a[root].v]-size[a[root].v];
	if(a[root].v!=0){
//		cout<<a[root].v<<"->"<<f[a[root].v]<<endl;
		ff(a[root].v);
	}
	return;
} 


int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].w>>a[i].u>>a[i].v;
		g[a[i].u]=1;
		g[a[i].v]=1;
	}
	memset(q,-1,sizeof(q));
	
	for(int i=1;i<=n;i++){
		if(g[i]==0){
			num=i;
			dfs(i,0);
			break;
		}
	}
	f[num]=size[num];
	ff(num);
	int ans=10000000;
	for(int i=1;i<=n;i++){
		ans=min(ans,f[i]);
		cout<<size[i]<<' ';
	}
//	cout<<ans;

/* 
	for(int i=1;i<=n;i++){
		cout<<size[i]<<' ';
	}
	*/
} 
 
2024/12/29 14:51
加载中...