题解

第五场 E.换根Dp

性质：

只要有一个权为$11$ 的边在点 $u,vu,v$ 之间在路径上，那么 $u,vu,v$ 之间的距离便是 $11$ , 否则是$22$。

思路 将所有能通过权为 $22$ 的边相连的点放入一个集合中。对于一个点 $uu$,

与其在相同集合中的点的距离为 $22$, 其所在集合大小记为 $siz{e}_{u}size\_u$ 则该集合的贡献为

$siz{e}_u\times 2-1size\_u\backslash times2\; -\; 1$, 与$uu$ 不在同一个集合中的点对答案的贡献为 $11$, 总贡献为$n-siz{e}_{u}n\; -\; size\_u$。

综上所述只要找到最小的 $siz{e}_{u}size\_u$ 即可。

实现技巧：

​ 可以利用面向对象的思想将并查集作为一个类对象封装起来。其属性包含了总的点的个数 $nn$ ,每个点所在集合的代表元 $pr{e}_{i}pre\_i$, 每个点所在集合的大小 $siz{e}_{i}size\_i$。支持三个操作，合并，查询代表元和所在集合的大小。

参考代码：

// 面向对象 封装并查集 太酷啦
class Dsu{
public:
    // 类成员
    vector<int> pre,size;
    // 类构造函数
    Dsu(int n):pre(n+1), size(n+1,1){
        // 初始化并查集 每个点的代表元是它自己
        // 自增赋值函数 在numeric 文件中
        iota(pre.begin(),pre.end(),0);
        size[0] = 0;
    }
    int find(int u){
        if(pre[u] != u){
            pre[u] = find(pre[u]);
        }
        return pre[u];
    }
    bool merge(int u,int v){
        u = find(u);
        v = find(v);
        if(u != v){
            size[v] += size[u];
            pre[u] = v;
            return true;
        }
        return false;
    }
    int Size(int u){
        u  = find(u);
        return size[u];
    }
};

void solve(){
    int n; cin >> n;
    Dsu dsu(n);
    for(int i =1; i < n; i++){
        int u,v,w;
        cin >> u >> v >>w;
        if(w == 2){
            dsu.merge(u,v);
        }
    }
    int min_size = 1e9;
    for(int i =1; i <= n; i++){
        min_size  =  min(min_size,
                     dsu.Size(i));
    }
    cout << (min_size-1)*2 + n-min_size << '\n';
}