1 月 6 日 CWOI 题解

比赛链接

这次三道题虽然没有什么特别难的知识点，但思维难度都不小，连神假仙都说 B 有难度，我在考试时打了三个暴力，结果最后居然排在第三名。。。

A. Last mile of the way

题目大意

给定一棵以 $1$ 为根的有根树，每个点有大小和权值，有 $q$ 次询问，每次询问从以点 $x$ 为根的子树中选出一些大小之和不超过 $s$ 的点，它们的权值之和最大是多少。

主要考点：树形 DP，dsu on tree。

思路

典型的树上背包。

由于这是一个静态问题，考虑先预处理出所有答案，然后再 $O(1)$ 回答。

我们枚举每个点，然后依次把它子树中的点塞进它的背包，每塞一个点显然是 $O(s)$ 的，所以这个算法复杂度为 $O(n^2s)$，显然最多只能过 $30\%$ 的数据（特判链的情况可以拿到 $50\%$），当然你也可以枚举每个儿子的子树，这样是 $O(ns^2)$ 的，还是没有办法 AC，所以我们考虑优化。

我们把两种算法合并一下，显然，我们可以直接把某一个儿子的答案作为初始答案，然后把其他的在这个点的子树中但不在这个儿子的子树中的点一个一个地塞进背包。

这里引出一个叫 dsu on tree 的东西，中文名叫树上启发式合并，它的核心思想跟上面说的那个合并之后的算法很像，都是把一个特定的儿子的答案拿来直接用，再枚举其他儿子，最终算出正确答案。

那么这个儿子到底是谁呢。

重儿子啊。

对于一个点来说，由于计算它的答案时是直接把重儿子的先拿来用，所以遍历重儿子的时间复杂度是 $O(1)$（准确来说我们并没有遍历它，只是先取了它的答案），而遍历轻儿子的时间复杂度是 $O(ns)$，乍一看这个算法好像还是 $O(n^2s)$ 的，但实际上它是 $O(ns\log n)$ 的。

接下来证明一下这个复杂度（以下内容借鉴了一下 OI Wiki）。

我们像树剖一样定义轻边和重边，显然，对于任意节点，从根到它的路径上的轻边数量不会超过 $\log n$，因为对于一个儿子，如果它是轻儿子，它的子树大小一定不超过它爸爸子树大小的一半，这样每次子树大小都除以 $2$，所以轻边数量不可能超过 $\log n$，而对于任意一个点来说，它会被点 $u$ 遍历，当且仅当它处在 $u$ 的轻儿子的子树中，也就是说，$u$ 连向这个儿子的边是一条轻边，但由于轻边数量不超过 $\log n$，所以它被遍历到的次数也不会超过 $\log n$，而每一次遍历遍历到它都需要 $O(s)$ 的时间，所以总时间复杂度为 $O(ns\log n)$。

参考代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define debug(x) cerr<<#x<<" = "<<x
using namespace std;
namespace IO
{
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define isdigit(c) (c>=48&&c<=57)
	#define isalpha(c) ((c>=65&&c<=90)||(c>=97&&c<=122))
	template<typename T> inline void read(T &x)
	{
		x=0;
		register int f=1;
		register char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
typedef long long ll;
const int N = 5e3+10, inf = 0x3f3f3f3f;
int n, q, ms, tot, w[N], a[N], siz[N], son[N], dfn[N], rk[N], x[N*20], s[N*20];
ll dp[N][N];
vector<int> edge[N];
void dfs1(int u, int f)
{
	siz[u] = 1;
	rep(i, 0, edge[u].size()-1)
	{
		int v = edge[u][i];
		if(v != f)
		{
			dfs1(v, u);
			son[u] = siz[son[u]] > siz[v] ? son[u] : v;
			siz[u] += siz[v];
		}
	}
}
void dfs2(int u, int f)
{
	tot++;
	dfn[u] = tot;
	rk[tot] = u;
	if(son[u])//借用树剖的思想
		dfs2(son[u], u);
	rep(i, 0, edge[u].size()-1)
	{
		int v = edge[u][i];
		if(v != f && v != son[u])
			dfs2(v, u);
	}
}
void dfs(int u, int f)
{
	if(son[u])
		dfs(son[u], u);
	rep(i, 0, ms)
		if(i >= a[u])
			dp[u][i] = max(dp[son[u]][i], dp[son[u]][i-a[u]]+w[u]);
		else
			dp[u][i] = dp[son[u]][i];
	rep(i, 0, edge[u].size()-1)
	{
		int v = edge[u][i];
		if(v != f && v != son[u])
			dfs(v, u);
	}
	if(son[u])
		rep(i, dfn[son[u]]+siz[son[u]], dfn[u]+siz[u]-1)
			per(j, ms, a[rk[i]])
				dp[u][j] = max(dp[u][j], dp[u][j-a[rk[i]]]+w[rk[i]]);
}
int main()
{
	read(n);
	rep(i, 1, n-1)
	{
		int u, v;
		read(u, v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	rep(i, 1, n)
		read(w[i], a[i]);
	read(q);
	rep(i, 1, q)
	{
		read(x[i], s[i]);
		ms = max(ms, s[i]);
	}
	dfs(1, 0);
	rep(i, 1, q)
		printf("%lld\n", dp[x[i]][s[i]]);
	return 0;
}

B. Reason For Living

题目大意

给定一张无向图，每次从这张图中选一个最大的生成森林，输出每条边应该被选到第几个生成森林中。

主要考点：并查集，二分答案。

思路

首先一个极大的生成森林应该是指从这张无向图的每个连通块中都任意找一棵生成树，这样的森林一定是最大的。

我们考虑把这些边一条一条地加入到这些生成森林中，由于每个森林的每个点的度都至少为 $1$（除开已经没有度的孤立点，这些点我们可以不管），所以对于一个度为 $d$ 的点来说，它的所有边一定会在前 $d$ 个森林中被选完。

由于我们首先保证编号靠前的森林是极大的，所以如果一条边可以被加入到某个森林中，它也一定可以被加入到后面的所有森林中。

那么这样就好办了，对于一条边，我们可以直接二分出它应该加入到哪一个森林中，用并查集来维护这个森林中的连通情况，就像 Kruskal 一样，但这样就又会有一个问题，并查集需要开多大？

看起来，并查集需要开 $nm$ 的空间，但仔细一想，由于一个点只会在前 $d$（它的度）个森林中出现，所以对于这个点，我们只需要 $d$ 的空间来存就行了，而无向图中点的总度数为 $2m$，所以我们只需要开 $2m$ 的空间就行了。

参考代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define min(a, b) (a < b ? a : b)
using namespace std;
namespace IO
{
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
	#define isdigit(c) (c>=48&&c<=57)
	#define isalpha(c) ((c>=65&&c<=90)||(c>=97&&c<=122))
	template<typename T> inline void read(T &x)
	{
		x=0;
		register char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
	}
}
using namespace IO;
typedef long long ll;
const int N = 1e6+10, inf = 0x3f3f3f3f;
int n, m, u[N], v[N], in[N], ans[N];
vector<int> f[N];
int find(int x, int p)
{
	return f[x][p] == x ? f[x][p] : f[x][p] = find(f[x][p], p);
}
int main()
{
	read(n);
	read(m);
	rep(i, 1, m)
	{
		read(u[i]);
		read(v[i]);
		in[u[i]]++;
		in[v[i]]++;
	}
	rep(i, 1, n)
	{
		f[i].push_back(0);
		rep(j, 1, in[i])
			f[i].push_back(i);
	}
	register int tot = 1;
	rep(i, 1, m)
	{
		register int l = 1, r = min(in[u[i]], in[v[i]]);
		while(l < r)
		{
			register int mid = (l+r)>>1;
			if(find(u[i], mid) == find(v[i], mid))
				l = mid+1;
			else
				r = mid;
		}
		register int t1 = find(u[i], l), t2 = find(v[i], l);
		f[t1][l] = t2;
		printf("%d\n", l);
	}
	return 0;
}

C. World Of Our Own

题目大意

给出一个长度为 $n$ 的序列 $a$，每次把这个序列的相邻两个数异或起来，形成一个新的长度为 $n-1$ 的序列，这样经过 $n-1$ 次操作之后就会得到一个长度为 $1$ 的序列，问每次操作之后的 $a_1$ 是多少。

主要考点：Lucas 定理，FWT。

思路

为了表述方便，我们把第 $i$ 步之后的 $a_1$ 记为 $b_i$，把原序列记为 $t$。

我们考虑一个数 $t_j$ 如何对 $b_i$ 做出贡献，显然，每次操作之后，我们相当于是把这个数向下走了一步，向左下走了一步，再和相同位置的数异或（感性理解一下，我语文比较差），这样的话，$b_i$ 中有多少个 $t_j$ 异或起来，就等价于 $t_j$ 有多少种方案数走到 $b_i$ 的位置，由于它一共走了 $i$ 步，向左下走了 $j-1$ 步，所以这个方案数就是 $\dbinom{i}{j-1}$（下面用 $k$ 来代替 $j-1$）。

这样的话，对于第 $i$ 步的 $a_1$，它的值应该是 $\dbinom{i}{0}$ 个 $t_1$，$\dbinom{i}{1}$ 个 $t_2$，$\dots$，$\dbinom{i}{n}$ 个 $t_n$ 异或起来。

由于一个数异或两次相当于没有异或，所以这里我们只关心 $\dbinom{i}{k}$ 的奇偶性，也就是 $\dbinom{i}{k}\mod 2$ 的结果，根据 Lucas 定理，它等价于这样。

$\dbinom{i_0}{k_0}\cdot\dbinom{i_1}{k_1}\cdot\dbinom{i_2}{k_2}\cdots\dbinom{i_p}{k_p}\mod 2$

其中 $i_p$ 和 $k_p$ 表示在二进制下 $i$ 和 $k$ 的第 $p$ 位。

如果这个式子最后的结果为 $0$，那么这个数就不会对 $b_i$ 做出贡献，反之则会，显然，只有当 $i_p=0$ 而 $k_p=1$ 时，$\dbinom{i_p}{k_p}\mod 2$ 才会为 $0$，我们可以把 $i$ 和 $k$ 的二进制类比为两个集合 $A$ 和 $B$，就像状压那样，根据上面的结论，能够做出贡献的一定满足 $B\supseteq A$，因此，我们就把问题转化成了求所有下标为 $i$ 的子集的数的异或和。

有一个叫 FWT 的算法能在 $O(n\log n)$ 的时间里解决这个问题，它的中文名是快速莫比乌斯变换，但实际上就是一个 DP。

我们设 $dp_{i,j}$ 表示下标为 $i$ 的子集，且低 $j$ 位与 $i$ 相同的数的异或和，则有递推公式如下。

$dp_{i,j}=\begin{cases}dp_{i,j+1} & (i_j=0)\\dp_{i,j+1}\oplus dp_{i-2^j,j+1} & (i_j=1)\end{cases}$

其中 $i_j$ 还是表示在二进制下 $i$ 的第 $j$ 位，初始化 $dp_{i,p}$（$p$ 表示 $i$ 的最高位，建议设成一个常数） 为 $t_i$，最后的答案为 $dp_{i,0}$，但由于 $dp_{i,j}$ 只与 $dp_{i,j+1}$ 有关，所以可以用滚动数组优化空间。

参考代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(register int i = (l); i <= (r); ++i)
using namespace std;
int dp[8388618];
int main()
{
	register int n, m = 1, t = 0, b, c, d;
	register long long ans = 0;
	scanf("%d%d%d%d%d", &n, &dp[0], &b, &c, &d);
	while(n > m)
		m <<= 1, t++;
	rep(i, 1, n-1)
		dp[i] = (1ll*dp[i-1]*(dp[i-1]+b)+c)%d;
	rep(j, 0, t)
		rep(i, 0, m)
			if((i>>j)&1)
				dp[i] ^= dp[i^(1<<j)];
	rep(i, 0, n-1)
		ans ^= dp[i]*(i+1ll);
	printf("%lld", ans);
	return 0;
}