回忆

· · 题解

O(n^2)

你发现 f_u 其实就是 u 到子树内节点的最大距离。暴力维护即可。期望得分 35。

O(n \log^2 n)

离线把树建出来。可以发现每加一个点相当于给一条链 +1。所以说每次你要干这个事情：

可以树剖套线段树二分简单做掉。直接维护 dep_u+f_u 可能会好写一点。期望得分 60。

O(n\log n)

毛毛虫坐火箭包。给 LCT、全局平衡二叉树、以及被卡常的正解。期望得分 70。

O(n)

树剖菜了，究其本质就是重链剖分跟这个 f_i 的相性不太好。那这个 f_i 的形式让你想到了什么？

考虑长剖，从叶子往根做，转而维护每个点加入时答案的变化量。对于每个点 u，我们维护 u 所在长链下方的所有节点的贡献。u 本身维护加法标记 t_u，下方的节点维护这个节点的实际 f 值与 t_u 的偏差值。

现在我们要处理 u 与短儿子 v 所有标记的合并。从上往下暴力枚举，对于同一深度的儿子，如果 u 一侧比 v 一侧的编号小，那么说明 u 这一侧比 v 这一侧先加入，上方的节点都已经被 u 修改掉，那么 v 已经没用，可以直接结算。否则，u 这边在 v 一侧之后、且深度小于等于他的标记全部都没用了，要将其全部结算，删除这些标记，再把 v 的标记插过来。

对于长儿子的继承，直接继承其加法标记，加上自己的 a_u，再将自己实际 f_u 与的 t_u 偏差值设为 -t_u 即可。

关于复杂度分析，标记的插入删除可以链表维护，由于长链维护的有效标记的数量不会大于长链长度，可以沿用长剖的复杂度分析，总复杂度 O(n)。

#include <bits/stdc++.h>

using namespace std;

// fastIO by d0j1a_1701

typedef long long ll;

const int MAXN = 5e6 + 10;
const int mod = 1e9 + 7;

inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); }

vector<int> g[MAXN]; int d[MAXN], md[MAXN], son[MAXN];

void init(int u) {
    for (int v : g[u]) {
        md[v] = d[v] = d[u] + 1, init(v);
        md[u] = max(md[u], md[v]);
        if (md[son[u]] < md[v]) son[u] = v;
    }
}

int n, a[MAXN], ans[MAXN], tag[MAXN];

struct node {
    int x, nxt;
    node() : x(0), nxt(0) {}
} l[MAXN];

void dfs(int u) {
    if (!son[u]) return ;
    dfs(son[u]), tag[u] = tag[son[u]], l[u].nxt = son[u];
    for (int v : g[u]) {
        if (v == son[u]) continue; dfs(v); int lst = u;
        for (int i = l[u].nxt, j = v; j; i = l[i].nxt, j = l[j].nxt) {
            if (i < j) ans[j] = add(l[j].x, tag[v]), lst = i;
            else {
                ans[i] = add(l[i].x, tag[u]);
                l[lst].nxt = j, swap(l[i].nxt, l[j].nxt);
                swap(i, j), lst = i;
                cadd(l[i].x, sub(tag[v], tag[u]));
            }
        }
    }
    cadd(tag[u], a[u]); if (tag[u]) l[u].x = mod - tag[u];
}

int main() {
    io.read(n, a[1]), n++;
    for (int i = 2, u; i <= n; i++) io.read(u, a[i]), g[u].emplace_back(i);
    init(1), dfs(1);
    for (int i = l[1].nxt; i; i = l[i].nxt) ans[i] = add(l[i].x, tag[1]);
    for (int i = 2; i <= n; i++) cadd(ans[i], ans[i - 1]), io.writeln(ans[i]);
}

这个放 T2 对洛谷来说可能还是有点超前了。