[Leaf] [P1395] 会议

p1395-会议---洛谷">P1395 会议 - 洛谷

1. 题面梗概

中译中： 在一棵树上找一个点，要求所有人到这个点的路程总和最小。如果这样的点有多个，输出编号最小的。

2. 逻辑推理

正儿八经的重心性质裸题。

特殊注意的，重心可能有两个，按照题目要求按字典序查询即可。

3. 代码实现

▶

AcCode

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

const int maxn = 5e4 + 50;

vector< int > adj[maxn];

int sz[maxn];
int f[maxn];
int dep[maxn];
int root;
int n;

void dfs( int u, int p )
{
    dep[u] = dep[p] + 1;
    for( int v : adj[u] )
    {
        if( v == p ) continue;
        dfs( v, u );
    }
}

void get_root( int u, int p )
{
    sz[u] = 1;
    f[u] = 0;

    for( int v : adj[u] )
    {
        if( v == p ) continue;
        get_root( v, u );
        sz[u] += sz[v];
        f[u] = max( f[u], sz[v] );
    }

    f[u] = max( f[u], n - sz[u] );
    if( root == 0 || f[u] < f[root] ) root = u;
    if( f[u] == f[root] ) root = min( root, u );
}

void solve( )
{
    cin >> n;
    for( int i = 1; i < n; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    get_root( 1, 0 );
    cout << root << ' ';

    dep[0] = -1;
    dfs( root, 0 );
    int ans = 0;

    for( int i = 1; i <= n; ++ i ) ans += dep[i];
    cout << ans << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( N )$。

• 关联笔记：直径与重心