Clock Tree[USACO 2020 February Silver]

题意

一个 $n$ 个点的树，点有点权 $a_i$，每次选择一个相连的点，每走一次到该点，该点的点权变为 $(a_i+1)modk$。

可以从任意点开始，任意点结束，能重复经过多次。

问有多少个出发点，满足最后存在一种方案使得点权均为 $0$。

原题：$n\le 2500,k=12$

加强版：$n\le 2\times {10}^6,k\le {10}^9$。

题解

Part 0:$n\le 2500$，必须走回出发点

首先必须明白一点，如果一条边的两端点全是 $0$，我们也还是可以走的。因为来回走 $k$ 次不就好了嘛。

假设枚举出发点，然后以该出发点为根。看子树内是否满足。

比较像树形DP的形式。

考虑DP的本质，是将一个大问题变成若干个子问题。

能否设置一个状态，表示子树内，除了这个点以外的点全变为 $0$ 后，该点还要变多少次才能变为 $0$。

转移的时候让父亲和儿子相互抵消，使得儿子变为 $0$，然后父亲此时的状态可以 $O(1)$ 计算。

显然是可以的。设为 $f_i$。

那么有：$f_u\equiv -a_u-\sum _{v\in so{n}_u}{f}_v(modk)$

最后必须满足 $f_{root}$ 为 $0$ ，$root$ 才能满足条件。

枚举 $root$，$O(n)$ 树形DP，计算是否可行。

Part 1:$n\le 2500$

是否能把上面的思路转移过来呢？

试一下吧。

还是枚举根节点（出发点）。

考虑最后一次经过根节点的情况，如果要满足条件，那么只能剩下一条 $k-1$ 的链，且此时根节点为 $0$。

如图所示：

那么可以发现，如果让链上最后两个 $k-1$ 相互抵消，那么一直抵消下去，最后最多剩下一个 $k-1$，再让这个 $k-1$ 和根节点相互抵消，此时根节点变为了 $1$。也就是说，根节点还需要 $k-1$ 次才变为 $0$。这种情况也是可以的，即 $f_{root}=k-1$。

时间复杂度 $O(n^2)$。

到这里就做完了原题。

Part 2:$n\le {10}^6$

显然换根DP就好了。

时间复杂度 $O(n)$，需要两遍dfs，常数有点大。

Part 3:$n\le 2\times {10}^6$

考虑转移方程到底是什么：$f_u\equiv -a_u-\sum _{v\in so{n}_u}{f}_v(modk)$。

假设以 $1$ 为根节点。

那么处于奇数层的 $u$ 的贡献是 $+a_u$，偶数层的 $u$ 的贡献是 $-a_u$。

而显然偶数层的点的最终答案是一样的。

奇数层的答案是偶数层的相反数。

因此直接暴算就好了，维护一下层数的奇偶性，就dfs也不用了。

这还是树形DP吗？

注意 $n=1$ 的特判。

时间复杂度 $O(n)$。

程序

#include <cstdio>
#define ll long long
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=2e6+5;
int n,k,a[N];
ll s1[2],s2[2],ans,tmp;
bool d[N];
int main()
{
	n=read(); k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	if(n==1) return printf("%d",(a[1]?0:1))&0;
	s1[0]++; s2[0]=a[1];
	for(int i=2;i<=n;i++)
	{
		d[i]=d[read()]^1;
		s1[d[i]]+=i,s2[d[i]]+=a[i];
	}
	tmp=(s2[1]%k-s2[0]%k+k)%k;
	if(tmp==0||tmp==k-1) ans+=s1[0];
	if(tmp==0||tmp==  1) ans+=s1[1];
	return printf("%lld\n",ans)&0;
}