题解 P3478 【[POI2008]STA-Station】

· · 题解

都是用动规做的大佬qwq

这题其实还有一种比较简单的做法

很明显答案只可能是树的直径两端点的其中一个 (⊙v⊙)嗯 就是酱紫!

O(n) (我也不知道为什么第9个点一直T?)

//BY ALways
#pragma GCC optimize (2)
#include<bits/stdc++.h>
#define M 1000005
#define il inline
#define ll long long
#define inf 0x7f7f7f7f
#define rep(i , x , y) for(register ll i = x ; i <= y ; ++i)
#define dor(i , x , y) for(register ll i = x ; i >= y ; --i)
using namespace std ;
ll n , x , y , k , rt , maxd , pos = 1 , d[M] , ans[M] , h[M] , nex[M << 1] , to[M << 1] ;
bool vis[M] ;
il ll re(){
    ll f = 1 , r = 0 ; char ch = getchar() ;
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1 ; ch = getchar();}
    while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0' ; ch = getchar();}
    return (r *= f) ;
}
il void add(ll u , ll v){
    nex[++k] = h[u] ; to[k] = v ; h[u] = k ;
} 
il void calc(){
    memset(vis , 0 , sizeof vis) ;
    ll A = 0 ;
    rep(i , 1 , n)A += d[i] ;
    if(A > x)x = A , y = rt ;
}
il void dfs(ll u , ll fa , ll dep){
    d[u] = dep ; if(dep > maxd)maxd = dep , pos = u ;
    for(ll i = h[u] ; i ; i = nex[i]){
        ll v = to[i] ;
        if(v == fa || vis[v])continue ; vis[v] = 1 ;
        dfs(v , u , dep + 1) ;
    }
}
int main(){
    n = re() ;
    rep(i , 1 , n - 1){
        x = re() ; y = re() ;
        add(x , y) ; add(y , x) ;
    }
    x = 0 ;
    maxd = 0 ; rt = pos ; dfs(rt , rt , 0) ; calc() ;
    maxd = 0 ; rt = pos ; dfs(rt , rt , 0) ; calc() ;
    maxd = 0 ; rt = pos ; dfs(rt , rt , 0) ; calc() ; 
    printf("%d\n",y) ;
    return 0 ;
}