求助,80pts,WA on #4 , #10
查看原帖
求助,80pts,WA on #4 , #10
667452
Null_in_null楼主2023/11/10 20:31
#include<bits/stdc++.h>
#define int long long
using namespace std ;

int n ; 
vector<int> tree[3000005] ;
int ans = -2147483647 ;
int id = 0 ;
int dp[1600005] ;
int dep[1600005] ;
int siz[1600005] ;

void dfs( int x , int pa ) {
	siz[x] = 1 ;
	dep[x] = dep[pa] + 1 ;
	for ( int i = 1 ; i < tree[x].size() ; i++ ) {
		int now = tree[x][i] ;
		if ( now == pa ) {
			continue ;
		}
		dfs( now , x ) ;
		siz[x] = siz[now] ;
	}
	return ;
}

void f( int x , int pa ) {
	for ( int i = 1 ; i < tree[x].size() ; i++ ) {
		int now = tree[x][i] ;
		if ( now == pa ) {
			continue ;
		}
		dp[now] = dp[x] + n - ( 2 * siz[now] ) ;//最关键!!把所有新根的子树减一,原根的子树加一 
		f( now , x ) ;
	}
	return ;
}

signed main( ) {//最近新会的用法(define int long long)
	cin >> n ;
	for ( int i = 1 ; i <= n ; i++ ) {//占位 
		tree[i].push_back(0) ;
	}
	for ( int i = 1 ; i < n ; i++ ) {//建立无向图 
		int u , v ;
		scanf( "%lld%lld" , &v , &u ) ;
		tree[v].push_back(u) ;
		tree[u].push_back(v) ;
	}
	dfs( 1 , 0 ) ;
	for ( int i = 1 ; i <= n ; i++ ) {
		dp[1] += dep[i] ;//第一个点的处理 
	}
	f( 1 , 0 ) ;
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( ans < dp[i] ) {
			ans = dp[i] ;
			id = i ;
		} 
	}
	printf( "%lld" , id ) ;
	return 0 ;
}
2023/11/10 20:31
加载中...