CF2143C：Max Tree题解

S1lver_W0lf · 2025-09-18 01:01:11 · 题解

CF2143C：Max Tree题解

题目大意：

给定一个有 n 个节点的树，编号从 1 到 n。每一条边包含了两个数 x 和 y。
构造一个从 1 到 n 的排列 p，其中 p_i 分配给节点 i。
对于每条边 (u, v)，其中 u < v，会关联两个数 x 和 y，这条边的贡献值的定义如下：

整个树的值为每条边的值相加。
请求出使整个树的值最小的排列 p。

思路

我想要每条边的值尽可能的小，但是又有一定约束性。赛时我就莫名联想到了差分约束，所以我就开始顺着这条线走下去。
对于图中的每个点，结合最小化贡献值，能够得到排列 p 中每一个元素的不等关系。于是想到：如果 x < y，则在最小化贡献的情况下，p_u 与 p_v 的大小关系应该是 p_u < p_v。此时可以从 u 向 v 引一条有向边，表示 p_u < p_v。否则就从 v 向 u 引一条有向边，表示 p_u > p_v。称新产生的有向图为 g。
可以发现，g 是一个有向无环图。因为原图为一个树，而树本身无环。我们连接的边相当于给树的每一条边定一个方向，所以在此过程中也不会产生环。所以图 g 是一个有向无环图。于是我们就可以给图 g 进行拓扑排序。
在拓扑排序时，新建一个变量 nw = 1，表示现在是排列 p 的第几个数。每当访问一个点，就将这个点的答案赋值为 nw，随后 nw++ 即可。
文字可能有点难以理解，接下来是代码。

代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 150;
vector <int> e[200010];
void solve(){
    int n;
    cin >> n;
    vector <int> d(n + 1), ans(n + 1, 0);//动态数组，方便初始化
    for(int i = 1; i <= n; i++)//初始化边数组
        e[i].clear();
    for(int i = 1; i < n; i++){
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        //根据题意，以及 x 和 y 的值，最小化边贡献
        if(x < y){
            d[v]++;
            e[u].push_back(v);
        }
        else{
            d[u]++;
            e[v].push_back(u);
        }
    }
    //以下是拓扑排序部分
    queue <int> q;
    int nw = 1;
    //将入度为 0 的节点入队
    for(int i = 1; i <= n; i++)
        if(!d[i])
            q.push(i), ans[i] = nw++;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v : e[u])
            if(!--d[v]){
                //如果删去当前边后，弧头指向的节点入度为 0，则入队
                q.push(v);
                ans[v] = nw++;
            }
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}
int T;
int main(){
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}