题解：AT_agc008_f [AGC008F] Black Radius

很好玩的题目！没有想到题解区做法，这里给一个鏖战许久的容斥做法（不知道为什么写了这么长）。

这个关键点、距离等限制有一种 [十二省联考 2019] 希望的既视感（虽然这个题更早）。直接算单个点的贡献就是以其为根时的最大深度，直接加起来会算重。

和希望那题一样，猜测对于一个树上连通块

S

，能染出来

S

的

u

在树上也是一个连通块。这应该是容易证明的，具体在下面的求解过程中也可以感知到。

先考虑

s_i=1

怎么做。

考虑容斥，可以直接套点边容斥，就是只需要算点的方案数减去边的方案数。更多关于这个结论的内容可以去希望的题解区。

点的方案数上面提过了，就是以其为根时的最大深度（根的深度为

1

）。

至于边的方案，考察树上一条边

(u,v)

，其中

u

是

v

的父亲：

令

x

表示在

v

子树外一点到

u

的最大距离，

y

表示在

v

子树内一点到

v

的最大距离。考虑选择

v,d_v

进行染色，是否存在

d_u

使得选择

u,d_u

染色的方案一样。建议画图感知一下下面的分讨。

若 $d_v<y$ ，此时必须有 $d_u=d_v+1$ ，否则在 $v$ 子树内的染色情况不同。那么这时必须要求 $d_v\geq x+1$ ，否则在 $v$ 子树外的染色情况不同。这种情况的方案数为 $\max(0,y-x-1)$ 。
若 $d_u<x$ ，此时必须有 $d_v=d_u+1$ ，否则在 $v$ 子树外的染色情况不同。同时有 $d_u\geq y+1$ ，否则在 $v$ 子树内的染色情况不同。这种情况的方案数为 $\max(0,x-y-1)$ ，可以看到和上面那种情况是恰好互补的。
若 $d_u=d_v$ ，这是唯一剩下的没有被上面讨论到的情况。此时取 $d_u=d_v=\max(x,y)$ 是唯一解，方案数为 $1$ 。

综合一下几种情况，一条边

u,v

的方案数为

\max(1,|x-y|)

。

自此解决了

s_i=1

的点，发现非常良心地有这档分（于是我以为我的思路是正解思路）。Code。

接下来考虑原题目。

原题目由于指定了关键点，容斥会有点麻烦。具体来说，不妨回归本源，钦定一些关键点

S

，算

S

合法的方案数并带上系数

(-1)^{|S|-1}

。

由于

|S|

合法等价于

|S|

的斯坦纳树合法，因此可以以树上连通块为计数对象。可以得到当且仅当一个树上连通块的叶子（度数

=1

）全都是关键点，且非叶点全都不是关键点的时候会有贡献。至于为什么是这样，在这里有详细的阐释。

将连通块上的所有点依次标号为

v_1,v_2,\cdots,v_k

。令

v_i

“子树”外最大距离为

x_i

，“子树”内最大距离为

y_i

。在此定义

v_i

的“子树”：对于一个点

w

，如果

v_i\rightarrow w

的路径上经过了除

v_i

以外的连通块上的点，

w

在

v_i

的“子树”外，否则在

v_i

的“子树”内。

再设

v_i

取

d_i

进行染色时

k

个点的染色结果相同。

从上面

s_i=1

的做法可以看出，只可能存在至多一个

i

满足

d_i<y_i

，在

d_i

确定后所有的

d

都确定了。同时有

d_i\geq x_i

，即

v_i

可以染到外面的所有点，否则外面的点染色情况不同。总的贡献为

\max(0,y_i-x_i)

。

于是可以发现对于一个连通块真正产生贡献的其实只有一个

v_i

，即

y_i

最大的那个。因为要求了

x_i\leq d_i< y_i

，又有

\forall i,j(i\not=j),x_i\geq y_j

，所以只有

y_i

最大的那个会产生贡献。注意到一个更强的说法是一个连通块内至多只有一个点满足

y_i>x_i

。

Caution：这里需要注意的是连通块的根如果是关键点，度数必须为

1

，否则度数必须不为

1

，不然与斯坦纳树的定义相悖。在下面的讨论中，默认这一条件已经考虑。

于是考虑分开计算每个满足

y>x

的点

u

的贡献。

对于一个在连通块上不为根的关键点 $u$ 来说，如果其子树外存在其它关键点，其容斥系数之和为 $-1$ ，否则为 $0$ 。这是因为假设其子树外有 $c$ 个关键点满足到 $u$ 的路径上没有其它关键点，容斥系数为 $\sum\limits_{i=1}^c(-1)^{i}\binom{c}{i}=-[c\not=0]$ 。
对于一个在连通块上为根的关键点来说，如果其子树内存在其它关键点，其容斥系数之和为 $-1$ ，否则为 $0$ 。
对于一个在连通块上的非关键点 $u$ 来说——这是最麻烦的情况，因为其“子树”内外的最大距离是不确定的——先再明确一遍其“子树”的定义：如果一个点到 $u$ 的路径上经过了除 $u$ 以外的连通块上的点，这个点在 $u$ 的“子树”外，否则在 $u$ 的“子树”内。由于子树内最大距离大于子树外最大距离才会产生贡献， $u$ 儿子（这里暂且以 $u$ 为根，就是将其原树上的父亲也视为儿子）的子树当中最大距离最大的那个一定会被划分到 $u$ 的“子树”内，而其它的儿子可以随意划分（当然只有在其子树内有关键点的时候才能被划分到 $u$ 的“子树”外）。然后再枚举“子树”外的最大距离计算贡献。假设“子树”外最大距离为 $d$ ，则考察是否存在至少两个子树内最大距离 $\leq d-1$ 的儿子有关键点，有的话容斥系数就是 $-1$ ，否则为 $0$ 。

注意还要考虑整个连通块不存在

d_i<y_i

的情况，这时等价于要求整棵树染色，在实现上可以先全部不管，最后再加上

1

。

总结一下，这个做法的关键在于容斥之后通过计数对象的转变（从集合到树上联通块再到点的贡献），容斥系数得到了极大的（？）简化，变成了便于计算（？）的形式。

更多细节可以看代码，其实很短。

CPP

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using LL = long long;
constexpr int MAXN = 2e5 + 5;
int n, mx[MAXN], smx[MAXN], out[MAXN], cnt_key[MAXN];
//子树内最大/次大，子树外最大，子树内关键点数 
vector<int> G[MAXN];
LL ans;
string S;
void dfs(int u, int fa) {
	cnt_key[u] += (S[u] == '1');
	for (int v : G[u]) if (v != fa) {
		dfs(v, u);
		cnt_key[u] += cnt_key[v];
		if (mx[v] + 1 > mx[u]) smx[u] = mx[u], mx[u] = mx[v] + 1;
		else smx[u] = max(smx[u], mx[v] + 1);
	}
}
void Get_out(int u, int fa) {
	if (S[u] == '1') ans += max(mx[u], out[u]);
	for (int v : G[u]) if (v != fa) {
		out[v] = max(out[u], mx[v] + 1 == mx[u] ? smx[u] : mx[u]) + 1;
		Get_out(v, u);
	}
}
void Get_ans(int u, int fa) {
	for (int v : G[u]) if (v != fa) Get_ans(v, u);
	if (S[u] == '1') {
		if (cnt_key[1] - cnt_key[u]) ans -= max(0, mx[u] - out[u]);//分讨情况：对于一个在连通块上不为根的关键点 u 
		for (int v : G[u]) if (v != fa && cnt_key[v]) ans -= max(0, (out[v] - 1) - (mx[v] + 1));//分讨情况：对于一个在连通块上为根的关键点 u 
	} else {
		//分讨情况：对于一个在连通块上的非关键点 
		G[u].emplace_back(0), mx[0] = out[u] - 1, cnt_key[0] = cnt_key[1] - cnt_key[u];//将原树上的父亲视为儿子 
		sort(G[u].begin(), G[u].end(), [&](int x, int y) { return mx[x] > mx[y]; });
		while (!G[u].empty() && !cnt_key[G[u].back()]) G[u].pop_back();
		int vismx = 0;//是否已经有比当前儿子子树最大距离更大的儿子被划分到 u 的“子树”内，如果有的话“子树”内最大距离是多少 
		for (int v : G[u]) if (v != fa) {
			if (vismx && cnt_key[v] && v != G[u].back()) ans -= max(0, vismx - (mx[v] + 1));
			vismx = max(vismx, mx[v] + 1);
		}
	}
}
int main() {
	IOS;
	cin >> n;
	for (int u, v, i = 1; i < n; ++i) cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
	cin >> S; S = '#' + S;
	dfs(1, 0), Get_out(1, 0), Get_ans(1, 0);
	cout << ans + 1 << '\n';
	return 0;
}

题解：AT_agc008_f [AGC008F] Black Radius

文章操作

相关推荐

评论

题解：AT_agc008_f [AGC008F] Black Radius