灾祸之六 无戮灾杰·艾斯迪亚

题目链接

一开始是在自习课上睡觉想出来的题，得到了qwaszx的肯定

在EZEC讨论群得到fyy的肯定，他想的做法和我一致，于是出完了数据，当时的思路是这样的

贪心，能移动一定会移动

考虑对于1号点的每个儿子为根的子树进行考虑，显然次数的瓶颈在于深度最深的点，那么先让一个深度最深的点一直移动直到进入1号点，之后每个时刻都会有点进入1号点了

于是计算一下最深的深度maxdep，子树内点的数量cnt，然后让某一个深度最深棋子畅通无阻得移动到1号点，计算这段时间内有棋子出去的时间戳数量，记为res，一棵子树的贡献就是maxdep+cnt-res

然后对1号点的所有子树贡献取一个max即可

宋队发现了这个题的原题，是某道ZR题，比这个题的区别在于棋子一旦开始走就不能停，且1号点只有一个儿子

这两个限制显然并没有影响，所以这两个题本质相同，但是ZR的那个题支持加入一个棋子，删除一个棋子

于是为了动态维护，这个题的做法基于上述思路就产生了不一样的解释方法

考虑每个棋子所在节点的深度$d_i$，每只棋子钦定一个$\leq d_i$的到达时刻，并且没有两只棋子的到达时刻相等

记深度为$i$的棋子个数为$cnt_i$，从小到大枚举$i$，先往栈里加入$cnt_i$个棋子，如果栈非空就从栈中弹出一个棋子

可以考虑用线段树维护$ans_i$表示考虑时刻$i$后还剩多少棋子，线段树二分查找某个位置后第一次出现连续两个$0$的位置和某个位置后第一个$0$即可

fyy给出了另一个容易维护的做法

记深度$\geq i$的棋子个数为$cnt_i$，深度$i$的贡献为$cnt_i + i - 1$，对所有深度求最大值即可

但由于zrzring想赶紧完结这个系列，于是就算是原题，那还是就这样了吧

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {
    int u, v, nxt;
} edge[N];

int n, m, cnt, head[N], ans, dep[N], vis[N], res, mx, tot[N];

void add(int u, int v) {
    edge[++cnt] = (EDGE){u, v, head[u]}; head[u] = cnt;
}

void dfs(int u, int last) {
    dep[u] = dep[last] + 1; if (vis[u]) mx = max(mx, dep[u]), cnt++, tot[dep[u]]++;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; if (v == last) continue; dfs(v, u);
    }
}

int solve(int u) {
    cnt = res = 0; dfs(u, 1);
    for (int i = 1; i <= mx - 1; i++) {
        if (!tot[i]) res++; tot[i + 1] += max(0, tot[i] - 1); tot[i] = 0;
    }
    tot[mx] = 0; if (cnt) cnt--;
    return mx + cnt - max(0, mx - 1 - res);
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) vis[read()] = 1;
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(); add(u, v); add(v, u);
    }
    for (int e = head[1]; e; e = edge[e].nxt) {
        int v = edge[e].v; ans = max(ans, solve(v));
    }
    printf("%d", ans);
    return 0;
}