cf1363 E. Tree Shuffling（树形dp）

题意：

树中的每个节点有花费val、初值t1和目标值t2。t1、t2只取0或1。

进行任意次操作，每次选择任一节点u和一个整数k，在u的子树（包括u）中任选k个不同节点，重新排列它们的t值，花费是 k*val(u)。问让所有节点的t值从初值变成目标值的最小花费。

思路：

如果一个点要从0变成1，另一个点要从1变成0，那就应该在这两个点的花费最小的公共祖先上操作。dfs1处理出每个点到根节点的路上的最小点权值 mi[u]。在从根节点出发的任一路上，mi肯定是递减的，这意味着如果某对能在 u 上花费 mi[u] 处理掉，就不用给 u 的祖先处理。

然后 dfs2(u)：如果u的子树中有x个0和y个1未处理，则马上在u上处理掉min(x,y) 对，再把没处理完的0或1上传给父节点。

#include 
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 4e5 + 5;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

int val[N], t1[N], t2[N];
int mi[N]; //i到根节点这条路上的最小值
void dfs1(int u, int fa)
{
    for(int i = h[u]; i; i = ne[i])
    {
        int v = e[i]; if(v == fa)  continue;
        mi[v] = min(mi[u], val[v]);
        dfs1(v, u);
    }
}

ll ans;
struct node{int x, y; }; //0的数量和1的数量
node dfs2(int u, int fa)
{
    int xx = 0, yy = 0;
    if(t1[u] != t2[u]) if(t1[u]) yy = 1; else xx = 1;

    for(int i = h[u]; i; i = ne[i])
    {
        int v = e[i]; if(v == fa) continue;
        node T = dfs2(v, u);
        xx += T.x, yy += T.y;
    }

    int small = min(xx, yy); //能处理就尽量处理
    xx -= small, yy -= small, ans += 2ll * mi[u] * small;
    return {xx, yy}; //返回剩下的未处理的点数
}

signed main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d%d", &val[i], &t1[i], &t2[i]);
    for(int i = 1, a,b; i < n; i++) scanf("%d%d", &a, &b), add(a,b),add(b,a);

    mi[1] = val[1], dfs1(1, -1);

    node T = dfs2(1, -1);

    if(T.x || T.y) ans = -1; //最后还是没处理完，无解
    printf("%lld", ans);

    return 0;
}