洛谷 P1131 题解

传送门

题意

有一棵 $n$ 个节点的以 $s$ 为根的树。每条树边都有一个长度。每次操作可以把一条树边的长度加 $1$。

问：至少操作多少次，可以使根节点到每个叶子节点的距离相等。

结论 $1$

对于任意子树，其根节点到其每个叶子节点的距离相等。

证明：
反证法。
设对于根为 $R$ 的树的根为 $r$ 的某一子树，有两个叶子 $a$、$b$ 到 $r$ 的距离不等。
那么不妨设节点 $x$ 与 $y$ 间的距离为 $dis(x,y)$，则有

$$dis(a,r)\not=dis(b,r)$$

所以

$$dis(a,r)+dis(r,R)\not=dis(b,r)+dis(r,R)$$

得

$$dis(a,R)\not=dis(b,R)$$

即 $a$、$b$ 到 $R$ 的距离不等。这与题目条件矛盾，所以命题成立。

解法

既然结论 $1$ 成立，那么先从最简单的情况入手。

如图，在这一棵以 $1$ 为根的树中，在操作后，根节点 $1$ 到叶子的距离最小是几？

很明显的，这个值应该是所有叶子到根的所有距离的最大值。

那么对于每个节点都实行此原则，就结束了。

Code：

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

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define int ll

int hd[500005<<1],nxt[500005<<1],to[500005<<1],we[500005<<1],et=0;
inline void adde(int u,int v,int w) { ++et,to[et]=v,we[et]=w,nxt[et]=hd[u],hd[u]=et; }
int n,s,ans,dp[500005];

void dfs(int u,int fa) {
    int mx=0,tot=0;
    for(int i=hd[u],v,t; v=to[i],t=we[i],i; i=nxt[i]) {
        if(v==fa) continue;
        dfs(v,u);
        if(dp[v]+t>mx) {
            ans+=(dp[v]+t-mx)*tot;
            mx=dp[v]+t;
        } else ans+=(mx-dp[v]-t);
        ++tot;
    }
    dp[u]=mx;
}

signed main() {
    cin>>n>>s;
    for(int i=1; i<n; ++i) {
        int u,v,t;
        cin>>u>>v>>t;
        adde(u,v,t); adde(v,u,t);
    }
    dfs(s,0);
    cout<<ans<<endl;
}