题解：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 染色的方案一样。建议画图感知一下下面的分讨。

综合一下几种情况，一条边 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 的贡献。

注意还要考虑整个连通块不存在 d_i<y_i 的情况，这时等价于要求整棵树染色，在实现上可以先全部不管，最后再加上 1。

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

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

#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;
}