Color the Tree

简单题。

HDU2013。

有 $n$ 个节点的树，边有颜色且带权，W 和 R 要在上面博弈。

一次博弈的结果定义为这样：

树初始所有边为白色，W 初始在 $a$，R 初始在 $b$。W 和 R 交替操作，W 先手。

每次若操作者为 W，则其可以选择一个与他目前节点 $x$ 的相邻的节点 $y$，满足 $x$ 到 $y$ 的边为白色或者红色，然后将这条边染红，接着 W 到 $y$。

否则若操作者 R，则其可以选择一个与他目前节点 $x$ 的相邻的节点 $y$，满足 $x$ 到 $y$ 的边为白色或者蓝色，然后将这条边染蓝，接着 R 到 $y$。

最终 $val_W$ 为所有红色边的权值和，$val_R$ 为所有蓝色权值和。

W 希望 $val_W$ 最大，R 希望 $val_R$ 最大，两人都绝顶聪明，那么这次博弈的结果为 $val_W$。

$m$ 次询问，第 $i$ 次询问给定 W 和 R 的初始点 $a,b$，求博弈结果。

$n,m\le 10^5$。

将 $a$ 到 $b$ 的路径单独拉出，那么其余的每一个点都可以视为路径上一个点的子树内节点，整体形状像一个“毛毛虫”。以下是洛谷图片：

。

那么显然的，只要 W 不停的从 $a$ 开始，向 $b$ 占领边，那么它占领的位置的左侧，R 都无法到达。那么 W 的最优策略就是不停的向 $b$ 走；同理，R 的最优策略是不停的向 $a$ 走。

那么最终的结果一定是：W 占领了一半的点（向上取整），R 占领了另一半的点。

由此，我们需要对于路径长度的奇偶性分类讨论。

Case #1：偶数长度

此时路径中点处 W 和 R 将会相交，而且都到达时 W 先手。

经过模拟后，可以发现，如果 W 到达了中点的一个儿子，那么这个儿子内部的所有边，R 无法到达；R 到达了中点的一个儿子，那么 W 也无法到达其子树内。

于是我们得出结论：W 和 R 应该交替选择中点的儿子中最大权值的儿子。

Case #2：奇数长度

奇数长度时同理，不过 W 和 R 到达同一个点时，R 先手，因此情况和上面完全相反。

那么这题就没了。

实现细节

首先你需要实现一个 lca(x,y) 函数，我是用树链剖分写的，主要是为了 $K$ 级祖先方便。

然后你需要实现 kth(x,k) 函数，求 $K$ 级祖先。以上两个函数都是用来求链中点的。

接着你要实现 pair<int,int> getnode(int x,int y,int t,int l,int len) 函数和 int getson(int x,int y)，功能分别是：

• 当链端点为 $x,y$，中点为 $t$，lca 为 $l$，长度为 $len$ 时，$t$ 在链上的前驱后继。求这个是为了求出将 $x,y$ 的链拉直时，$t$ 的子树包含了谁（就是 $t$ 的所有邻边中去掉其前驱后继后的所有邻边）。
• 求出 $x$ 在 $y$ 方向的儿子，使用树链剖分可以方便求解。这个函数是辅助 getnode 函数的。

给出一个 getnode 的实现：

pair<int,int>getnode(int x,int y,int t,int l,int len){
	if(t==l)return {getson(t,x),getson(t,y)};
	if(lca(y,t)!=t)return {getson(t,x),f[t]};
	return {f[t],getson(t,y)};
}

以上是所有的辅助函数。

在查询的时候，你需要先求出链中点 $t$，链 lca $l$ 以及长度 $len$。

接着调用 getnode 获得 $t$ 的前驱后继 $X,Y$。

最后你需要求出这样一个东西：去掉 $X,Y$ 后，$t$ 邻边中的子树大小（这个一共有 $\mathcal{O}(n)$ 个，可以预处理）从大到小排序后，交替求和的两个求过分别是多少。

你可以直接写一个动态开点线段树维护这个东西，十分好写。注意删除 $X,Y$ 后要恢复贡献。

注意特判 $len=0/1$，特殊处理一下即可。

然后这道题就做完了。

PS: 这题卡空间，要离散化。