CF1916E Happy Life in University

· · 题解

想题五分钟，卡常五小时/fn/fn/fn/oh/oh/oh 诋毁出题人！！

upd 2024.1.10：我错了对不起出题人，我深深忏悔，原因是我下面第一份写的看似正确的代码实际上复杂度假了。

个人觉得比 D 简单几十倍啊，D 可以定性为：天赋哥题。相比之下这个题就比较不需要脑子。

我们考虑怎么去数一条自上而下的链上的不同权值数量，这个是非常非常经典的 trick 啊：记录 lst_u 表示 u 往上跳达到的第一个权值与其相同的结点，则一条自上而下的链 u\to v 上权值的数量就是 u\to v 这条链上 lst 在 u 上面的结点个数。这个 lst 我们可以 dfs 一次去算出来。

void dfs1(int u) {
    int l = bk[a[u]];
    lst[u] = l;
    bk[a[u]] = u;
    for (int v : g[u]) dfs1(v);
    bk[a[u]] = l;
}

考虑去枚举这个 lca，然后考虑去维护一下子树里面每个点到当前 lca 的权值种数 cnt_i，即每个点到 lca 的路径上有多少个点在 lca 之上。我们考虑把递推式地维护，即从 fa 来转移到 u，容易发现相当于把 lst=fa 的点的子树内 cnt_i 全部加一；查询就是查各个子树内点 cnt 的最大值减去 cnt_{fa}，即查询链和。这也是经典问题了，我们 dfs 一下处理出每个点被遍历到的时间，那么一个子树内的时间一定是连续的，我们就可以用区间加区间 \max 的一个线段树去维护之。每个点只会被加一次减一次查询两次，复杂度是严格的 \Theta(n\log n)。

void dfs1(int u) {
    dfn[u] = ++idx, siz[u] = 1;
    p[lst[u] = bk[a[u]]].push_back(u);
    int l = bk[a[u]];
    bk[a[u]] = u;
    for (int v : g[u]) dfs1(v), siz[u] += siz[v];
    bk[a[u]] = l;
}

void dfs2(int u, int fa) {
    for (int y : p[fa]) add(rt, dfn[y], dfn[y] + siz[y] - 1, 1);
    int mx = 1, sc = 1;
    int q = fa ? query(rt, dfn[fa], dfn[fa]) : 0;
    for (int v : g[u]) {
        int y = query(rt, dfn[v], dfn[v] + siz[v] - 1) - q;
        if (y > mx) sc = mx, mx = y;
        else if (y > sc) sc = y;
    }
    for (int v : g[u]) dfs2(v, u);
    if ((ll) mx * sc > ans) ans = (ll) mx * sc;
    for (int y : p[fa]) add(rt, dfn[y], dfn[y] + siz[y] - 1, -1);
}

然而善良美好的出题人并不愿意让我们这样轻而易举地通过这道题，所以在这样一个线段树跑 3\times 10^5 的时候贴心地为我们设置了 1s 的时限，使得我们最终止步于 #35 号点。

upd：上面那份代码复杂度假了。可以不用看了。

卡常！经过我真挚诚恳的求问，最终得到了 \text{{D}\red{itaMirika}} 大神的通过代码，我对着修改了几处地方，直接 436ms 通过了此题。

具体地：

void dfs1(int u) {
    dfn[u] = ++idx, siz[u] = 1;
    int l = bk[a[u]];
    lst[u] = l;
    bk[a[u]] = u;
    for (int v : g[u]) dfs1(v), siz[u] += siz[v];
    bk[a[u]] = l;
}

void dfs2(int u, int fa) {
    for (int v : g[u]) dfs2(v, u);
    add(rt, dfn[u], dfn[u] + siz[u] - 1, 1);
    for (int y : p[u]) add(rt, dfn[y], dfn[y] + siz[y] - 1, -1);
    int mx = 1, sc = 1;
    int q = fa ? query(rt, dfn[fa], dfn[fa]) : 0;
    for (int v : g[u]) {
        int y = query(rt, dfn[v], dfn[v] + siz[v] - 1) - q;
        if (y > mx) sc = mx, mx = y;
        else if (y > sc) sc = y;
    }
    if ((ll) mx * sc > ans) ans = (ll) mx * sc;
    p[lst[u]].push_back(u);
}

首先把儿子优先扔下去 dfs，然后把 u 子树 +1，因为儿子优先递归，所以相当于这个点子树里面所有点的子树都 +1；然后我们把 lst=u 的点的子树全部 -1，实际上进行到 u 的时候就是 u 子树内所有 lst 在 u 子树内的点的子树全部 -1，那么剩下的没被 -1 的只有可能 lst 在 u 的上面；这样足以通过此题。

老话说得好：细节决定成败。常数这种东西看似细枝末节，而许许多多的人都在编写代码的过程中忽略了自己的常数，而这样的小细节才是出题人要求选手达到的境界。这也侧面反映出作为一名 OI 选手，我的 OI 造诣和自我修养不足，理解不了这种内在的阳春白雪的高雅艺术，只能看到外表的辞藻堆砌，参不透其中深奥的精神内核，我整个人的层次就卡在这里了，只能度过一个相对失败的人生。希望大家引以为戒。在此，我深深忏悔，并收回文章开头对出题人的诋毁，非常好题目，为出题人点赞。

2024.1.10 反转了，复杂度假了。老话说得好，复杂度决定成败，后面忘了，希望大家能自行补全。