526互联

The 1st Universal Cup Stage 12: ̄Ookayama, April 15-16, 2023 Problem A. XOR Tree Path

发布时间 2023-04-17 00:40:27作者: 景苌_M

 

 

 

 

 

  • 题意
    　　给定一颗树，对于每个节点有一个颜色(白色或者黑色)，对于一个操作：选择一个叶子节点，对于从叶子节点到根节点路径上的所有颜色反转（黑变白，白变黑）。
    让你求出使用任意次操作后，整个树上黑色节点最多有多少个。

  • 思路
    对于每个节点在最终状态有两种结果，一个是不变，一个是反转颜色。如果颜色反转，则在这个节点的子树里，我们选择了奇数个叶子节点进行操作（显然，偶数次的操作经过一个节点不会改变该节点颜色）。这时我们可以设置f[N][2]表示对于每个节点，在其子树选择叶子节点的奇偶性可以获得的最大黑色数量。


  • 代码
     
    #include<bits/stdc++.h>
using LL = long long;
constexpr int N = 2e5 + 7;
constexpr int M = 1e6 + 7;
constexpr int MOD = 1e9 + 7;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr LL INF = 0x3f3f3f3f3f3f3f3f;
std::vector<int>e[N];
int f[N][2];
int a[N], in[N];
int n;
struct CNM {
  int ji, ou;
  bool operator < (const CNM &a) const {
    return (ji - ou) > (a.ji - a.ou);
  }
};
void dfs(int u, int fa) {
  if (u != 1 && in[u] == 1) {
    f[u][0] = a[u];
    f[u][1] = (a[u] ^ 1);
    return;
  }
  std::vector<CNM> t; 
  bool ok = true;
  for (int v : e[u]) {
    if (v == fa) continue;
    dfs(v, u);
    if (f[v][0] != -1 && f[v][1] != -1)ok = true, t.push_back({f[v][1], f[v][0]});
  }
  if (!ok) return;
  std::sort(t.begin(), t.end());
  int res = 0;
  for (auto [x, y] : t) res += y;
  int cnt = 0;
  int ji = 0, ou = res;
  for (auto [x, y] : t) {
    cnt ++;
    res += x;
    res -= y;
    if (cnt & 1) ji = std::max(ji, res);
    else ou = std::max(ou, res);
  }
  f[u][1] = (a[u] ^ 1) + ji;
  f[u][0] = a[u] + ou;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) f[i][1] = -1, f[i][0] = -1;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];  
  for (int i = 1, u, v; i <= n - 1; ++i) {
    std::cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
    in[u] ++;
    in[v] ++;
  }
  dfs(1, 0);
  std::cout << std::max(f[1][1], f[1][0]) << '\n';
  return 0;
}