[Leaf] P2726 树的双中心

p2726-[shoi2005]-树的双中心---洛谷">P2726 [SHOI2005] 树的双中心 - 洛谷

1. 题面梗概

中译中： 在一棵带有节点权值 $W(v)$ 的树上选两个中心点 $x$ 和 $y$，最小化所有点到距离其最近中心的权值距离之和。

即最小化下方柿子：

$$S(x,y)=\sum_{v\in V} (W(v)\cdot \min\{d(v,x),d(v,y)\})$$

2. 逻辑推导

既然是两个点，我们就假设这两个点为 $A$ 和 $B$，由于每个点都会找到一个最近的位置，不妨将图上的节点划分为两个集合 $A$ 和 $B$。

而树有一个特别的性质，$n$ 个点只有 $n-1$ 条边，所以我们可以把问题转化为，删除树上的某一条边，然后分别求出两棵子树的重心。

2.1 重心

这题麻烦的一点在于，点是存在点权的，没法直接套用 重心的模板。

重心的定义由“子树大小”演变为“子树权值和”。

但是同 P5666 树的重心 的逻辑，带权重心在树上具有单调移动的性质。

• 假设当前的点为 $u$，当前连通块的总权值为 $sz\_sum$。

• 当我们向子节点 $v$ 移动时，总距离和的变化量为：

$$nxt\_val = cur\_val + (sz\_sum - sz[v]) - sz[v] = cur\_val + sz\_sum - 2sz[v]$$

结论：只要某个 子树权值和 $sz[v]$ 满足 $sz\_sum < 2sz[v]$，那么向该方向移动一定会让总距离变小。（公式写的很明白了）

2.2 路径

理论上这题也可以采用倍增优化，但是题目限定了 $H \leq 100$，所以我们可以直接暴力向下搜索，沿着满足条件的边找就可以了。

复杂度为 $O(N \cdot H)$，在这个数据规模下，很稳定。（我甚至都怀疑是出题人故意为之的）

再补充一点小细节，因为高度不大，所以这图没必要先找到根节点，再建图。直接以 $1$ 为根节点跑一遍就行了，每次切割 $(u,v)$ 之后，将图分为 $1 \to u$ 和 $v \to n$ 两个连通块处理即可。

2.3 结论

是重心性质的变体，带权重心。

3. 代码实现

▶

AcCode

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

const int maxn = 5e4 + 50;
const ll inf = 1e18;

struct Edge { int u, v; };

vector< int > adj[maxn];
vector< Edge > edges;

ll sz[maxn], val[maxn];
int dep[maxn], fa[maxn], w[maxn];
int son1[maxn], son2[maxn];
int n;

// 预处理
void dfs( int u, int p, int d )
{
    sz[u] = w[u];
    val[u] = 0;
    dep[u] = d;
    fa[u] = p;
    son1[u] = son2[u] = 0;
    
    for( int v : adj[u] )
    {
        if( v == p ) continue;
        dfs( v, u, d + 1 );

        sz[u] += sz[v];
        val[u] += val[v] + sz[v];

        if( sz[v] > sz[son1[u]] ) son2[u] = son1[u], son1[u] = v;
        else if( sz[v] > sz[son2[u]] ) son2[u] = v;
    }
}

void calc( int u, ll cur_val, int sz_sum, int del, ll &res )
{
    res = min( res, cur_val );

    int son = son1[u];
    // 若重儿子被切割了，或者次重儿子因为切割边更重了，切换
    if( son1[u] == del || ( son2[u] && sz[son2[u]] > sz[son1[u]] ) ) son = son2[u];

    if( son == del || son == 0 ) return;

	// 回顾上文代价函数对比，就知道为什么这么判断了
    if( sz[son] * 2 > sz_sum )
    {
        calc( son, cur_val + sz_sum - 2 * sz[son] , sz_sum, del, res );
    }

}

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 );
        edges.push_back({ u, v });
    }

    for( int i = 1; i <= n; ++ i ) cin >> w[i];

    dfs( 1, 0, 0 );

    ll ans = inf;

    for( auto [u, v] : edges )
    {
        if( fa[v] != u ) swap( u, v );

        for( int cur = u; cur; cur = fa[cur] ) sz[cur] -= sz[v];

        ll res_up = inf, res_down = inf;

        ll cost = val[1] - ( val[v] + sz[v] * dep[v] );

        calc( 1, cost, sz[1], v, res_up );
        calc( v, val[v], sz[v], 0, res_down );

        ans = min( ans, res_up + res_down );

        for( int cur = u; cur; cur = fa[cur] ) sz[cur] += sz[v];
    }
    cout << ans << '\n';
}

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

复盘

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

• 碎碎念：在有权图中，重心的判定条件是 $\max(sz_{child}, sz_{total} - sz_u) \le sz_{total} / 2$。

• 关联笔记：直径与重心