MX Day 14

· · 生活·游记

T1:

思路：

这道题肯定是树上动态规划，因为涉及到了非常经典的换根问题（我当时在做的时候没有下定决心，一直在想别的）；

首先，我们发现题目中的贡献是子树所有节点到这个点的边权按位或的值，这个值之和就是答案。所以，我们这样想：

因为我们换根反正是将一棵树的贡献移到另外一棵树上去，然后将一定量的贡献减去，所以我们关注每一位，以每一位为出发点；

我们首先将每一个点的子树大小和每一位对于子树的贡献次数算出来，用两个DFS，之后，我们就要考虑核心的换根，了，而且非常困难；

首先，计算贡献数组gx，当我们发现这条边的这一位是1，则很简单，它的所有子节点全部都会在这一位上给予贡献，所以我们直接+=siz[y]，否则，我们就要继续递归，加上它的这条边下面的节点的gx[y]。

之后，就是困难的更换根节点，首先，我们要明白一个非常重要的概念：换根本质上是将目标节点的子树答案保留，将这棵树除这颗子树之外的所有节点的贡献全部加到这个点上去，这就是换根的灵魂。想清楚这个就好办了，首先如果这条边这一位是1，那么很简单，其他的点都会给它贡献，将add变成n-siz[y]，否则，我们就要考虑得深一点，因为我们知道每次换根它的add都是继承自上一次的结构，形象化的说，我们每次的更新就是将除这颗子树之外是否还有节点能新增贡献，但是我们一开始的gx数组记录的是1为根节点的情况，所以必须在每次跟新新的add时加上原来的add，毕竟之后的答案也会将原来已经转下去的点的贡献加上嘛。

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
struct node
{
    int to, next, val;
} edge[1000009];
int head[1000009], cnt = 0;
void add(int u, int v, int w)
{
    edge[++cnt] = (node){v, head[u], w};
    head[u] = cnt;
}
int dp[1000009];
int n, m;
int siz[1000009], gx[1000009];
void dfs(int x, int fa)
{
    siz[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        // int w = edge[i].val > & 1;
        if (v == fa)
        {
            continue;
        }
        dfs(v, x);
        siz[x] += siz[v];
    }
}
void dfs1(int x, int fa, int wz)
{
    gx[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        int w = (edge[i].val >> wz) & 1;
        if (y == fa)
        {
            continue;
        }
        dfs1(y, x, wz);
        if (w)
        {
            gx[x] += siz[y];
        }
        else
        {
            gx[x] += gx[y];
        }
    }
}
void dfs2(int x, int fa, int wz, int add)
{
    dp[x] += (1 << wz) * (add + gx[x]);
    for (int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        int w = (edge[i].val >> wz) & 1;
        if (y == fa)
        {
            continue;
        }
        int sum = 0;
        if (w)
        {
            sum = n - siz[y];
        }
        else
        {
            sum = add + gx[x] - gx[y];
        }
        dfs2(y, x, wz, sum);
    }
}
void init()
{
    for (int i = 1; i <= n + n; i++)
    {
        gx[i] = dp[i] = siz[i] = 0;
        head[i] = 0;    
    }
    cnt = 0;
}
void work()
{
    n = read();
    init();
    for (int i = 1; i < n; i++)
    {
        int x = read(), y = read(), w = read();
        add(x, y, w);
        add(y, x, w);
    }
    dfs(1, 0);
    for (int i = 0; i <= 32; i++)
    {
        dfs1(1, 0, i);
        dfs2(1, 0, i, 0);
    }
    int minn = 1e18;
    for (int i = 1; i <= n; i++)
    {
        minn = min(minn, dp[i]);
    }
    printf("%lld\n", minn);
}
signed main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int T = read();
    while (T--)
    {
        work();
    }
    return 0;
}

T2……