A Odd Selection

这个 $a$ 一开始想的分类讨论然后没有考虑 $x$ 的奇偶，其实 $n$ 不大，直接枚举奇数的个数就行。

AC代码：

const int N = 5e5 + 50;
int n, m, k;
int a[N];int main()
{int T;sd(T);while (T--){sdd(n, m);rep(i, 1, n)sd(a[i]);int e = 0, o = 0;rep(i, 1, n){if (a[i] & 1)o++;elsee++;}bool flag = 0;rep(i, 0, min(m, o)){if (m - i <= e && (i & 1)){flag = true;break;}}if (flag)puts("Yes");elseputs("No");}return 0;
}

B Subsequence Hate

子序列中不能出现 $101$ 和 $010$ , $s$ 最终只有四种情况，$00..0011..11$ 和 $11..1100..00$ 和 $1111...111$ 和 $000...00$ 。

$01$ 和 $10$ 这种就是枚举分界线，找到最小的。

AC代码：

string s;int main()
{int T;sd(T);while (T--){cin >> s;int len = s.size();int zero = 0, one = 0;int zero1 = 0, one1 = 0;rep(i, 0, len - 1){if (s[i] == '0')zero++;elseone++;}int ans = len;rep(i, 0, len - 1){ans = min(ans, min(zero, one) + min(zero1, one1));if (s[i] == '0')zero1++, zero--;elseone1++, one--;}pd(ans);}return 0;
}

C. Game On Leaves

当 $x$ 点入度为 $1$ 或 $0$ 时，一定是先手直接可以删除这个点。双方都会尽量不让 $x$ 节点的度变成小于等于 $1$，因此这个 $x$ 节点都是倒数第二个取走的。所以判断 $n$ 的奇偶性就行了。

AC代码：

int n, m, x;
int main()
{int T;sd(T);while (T--){sdd(n, x);int cnt = 0;rep(i, 1, n - 1){int u, v;sdd(u, v);if (u == x || v == x)cnt++;}if (cnt <= 1 || n % 2 == 0)puts("Ayush");elseputs("Ayush");}return 0;
}

E. Tree Shuffling

有一个 $n$ 个节点的数，每个节点有一个代价和当前值还有最后要变成的值，可以任意选择一个根节点 $u$ 然后选择他的的 $k$ 个子节点，这些节点的值可以互换，代价是 $k*a_u$ ，求把全部节点值变成期望值的最小代价。

让儿子的费用赋值为 $min$ (儿子费用,父亲费用)，这样操作的好处是，如果儿子所在的子树存在需要互换的两个节点，那一定是儿子解决这个问题而不是去麻烦父亲乃至祖宗

因此只要统计每个子树的需要把 $0$ 变 $1$ 的节点个数，以及 $1$ 变$ 0$ 的节点个数，然后计算费用，然后把这两个值传给父亲即可。

AC代码;

const int N = 2e5 + 10;
int n, x;
vector<int> a[N];
int cost[N], b[N], c[N],cnt[N][2];
ll ans;void dfs(int x, int fa)
{if (fa != -1)cost[x] = min(cost[x], cost[fa]);for (auto p : a[x]){if (p != fa){dfs(p, x);cnt[x][0] += cnt[p][0];//0变1的个数cnt[x][1] += cnt[p][1];//1变0的个数}}if (b[x] != c[x])cnt[x][b[x]]++;int t = min(cnt[x][0], cnt[x][1]);ans += 2ll * t * cost[x];cnt[x][0] -= t;cnt[x][1] -= t;
}
int main()
{sd(n);rep(i, 0, n-1)sddd(cost[i], b[i], c[i]);rep(i, 1, n - 1){int u, v;sdd(u, v);u--,v--;a[u].pb(v);a[v].pb(u);}dfs(0, -1);if (cnt[0][0] || cnt[0][1])puts("-1");elsepld(ans);return 0;
}