测试数据 4

10
1 2 3 4 5 6 7 8 9 10
1 10
1 2
1 3
2 4
2 6
3 5
3 7
8 6
5 9

9
7
7
1
3
3
1
1
1
0

树上差分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000;
int n;
int a[MAXN + 5];
vector<int> e[MAXN + 5];
// -------start LCA--------
// f[i][j] 记录 i 的 2^j 级别祖先
int f[MAXN + 5][25];
// dep[i] 求节点 i 的深度
int dep[MAXN + 5];
void dfs(int u, int fa)
{
    f[u][0] = fa;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
void init(int s)
{
    dep[s] = 0;
    dfs(s, 0); // 预处理深度 dep[u]，以及一级祖先 f[u][0]
    // i 的 2^j 级别祖先 = i 的 2^{j-1} 级别祖先的 2^{j-1} 级别祖先
    for (int j = 1; (1LL << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j - 1]][j - 1];
}
// lca(u,v) 返回 u,v 的最近公共祖先
int lca(int u, int v)
{
    // 保证 u 在上面，v 在下面
    if (dep[v] < dep[u])
        swap(u, v);
    // 拉到同样的深度
    for (int j = 20; j >= 0; j--)
        if (dep[v] - dep[u] >= (1 << j))
            v = f[v][j];
    // 初始两点之间是祖孙关系时，拉到同样深度就会变成同一个点
    if (u == v)
        return u;
    // 同步往上走，跳到了 lca 下面一跳位
    for (int j = 20; j >= 0; j--)
        if (f[u][j] != f[v][j])
            u = f[u][j], v = f[v][j];
    return f[u][0];
}
// -------end LCA--------
// 树上差分数组
// 每个节点的真实权值为子树所有节点的 d 之和
int d[MAXN + 5];
void dfsSum(int u, int fa)
{
    // sum[u] = d[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfsSum(v, u);
        d[u] += d[v];
        // sum[u]+=sum[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // ----- start LCA 预处理 -----
    init(1);
    // ----- end LCA 预处理 -----
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        u = a[i];
        v = a[i + 1];
        // [u, v) 路径 +1
        // 先对 [u, v] 路径 +1
        int uv = lca(u, v);
        d[u]++, d[v]++, d[uv]--, d[f[uv][0]]--;
        // 对 v 单点 -1
        d[v]--, d[f[v][0]]++;
    }
    dfsSum(1, 0);
    for (int i = 1; i <= n; i++)
        cout << d[i] << "\n";
    return 0;
}

树链剖分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300000 + 5;
int n;
vector<int> e[MAXN];
int a[MAXN];   // 旅行路线
int ans[MAXN]; // 最终答案
// 每个点的：父节点、深度、大小、重子节点
int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN];
void dfs_build(int u, int fat)
{
    hson[u] = 0;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fat)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs_build(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
// 每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
int tot, top[MAXN], dfn[MAXN], rnk[MAXN];
void dfs_div(int u, int fa)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u])
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fa || v == hson[u])
                continue;
            top[v] = v;
            dfs_div(v, u);
        }
    }
}
struct SegTree
{
    int sum[4 * MAXN], lazy[4 * MAXN];
    void up(int now)
    {
        sum[now] = sum[now * 2] + sum[now * 2 + 1];
    }
    void down(int now, int l, int r)
    {
        if (l == r)
            return;
        int mid = (l + r) / 2;
        sum[now * 2] = sum[now * 2] + (mid - l + 1) * lazy[now];
        sum[now * 2 + 1] = sum[now * 2 + 1] + (r - mid) * lazy[now];
        lazy[now * 2] = lazy[now * 2] + lazy[now];
        lazy[now * 2 + 1] = lazy[now * 2 + 1] + lazy[now];
        lazy[now] = 0;
    }
    void build(int now, int l, int r)
    {
        lazy[now] = 0;
        if (l == r)
        {
            sum[now] = 0; //--------
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid);
        build(now * 2 + 1, mid + 1, r);
        up(now);
    }
    void add(int now, int l, int r, int x, int y, int z)
    {
        if (x <= l && r <= y)
        {
            sum[now] = sum[now] + (r - l + 1) * z;
            lazy[now] = lazy[now] + z;
            return;
        }
        down(now, l, r);
        int mid = (l + r) / 2;
        if (x <= mid)
            add(now * 2, l, mid, x, y, z);
        if (y >= mid + 1)
            add(now * 2 + 1, mid + 1, r, x, y, z);
        up(now);
    }
    int query(int now, int l, int r, int x, int y)
    {
        if (x <= l && r <= y)
            return sum[now];
        down(now, l, r);
        int mid = (l + r) / 2;
        int res = 0;
        if (x <= mid)
            res = res + query(now * 2, l, mid, x, y);
        if (y >= mid + 1)
            res = res + query(now * 2 + 1, mid + 1, r, x, y);
        return res;
    }
} st;
// u~v路径上点都加1
void update(int u, int v)
{
    st.add(1, 1, tot, dfn[v], dfn[v], -1);
    int res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
        {
            // v~top[v] 计入答案中
            st.add(1, 1, tot, dfn[top[v]], dfn[v], 1);
            v = fa[top[v]];
        }
        else
        {
            // u~top[u] 计入答案中
            st.add(1, 1, tot, dfn[top[u]], dfn[u], 1);
            u = fa[top[u]];
        }
    }
    if (dep[u] > dep[v])
        swap(u, v);
    st.add(1, 1, tot, dfn[u], dfn[v], 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[1] = 1;
    fa[1] = 0;
    dfs_build(1, 0);
    tot = 0;
    top[1] = 1;
    dfs_div(1, 0);
    //--------
    st.build(1, 1, tot);
    for (int i = 1; i <= n - 1; i++)
        update(a[i], a[i + 1]);
    for (int i = 1; i <= n; i++)
        cout << st.query(1, 1, tot, dfn[i], dfn[i]) << "\n";
    return 0;
}

dfs里面初始化dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500000;
int n, m, s;
vector<int> e[MAXN + 5];
int dep[MAXN + 5];
int lg[MAXN + 5];
int f[MAXN + 5][32];
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i <= lg[dep[u]]; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y])
        x = f[x][lg[dep[x] - dep[y]] - 1];
    if (x == y)
        return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
int a[312345];
int ans[312345];
void dfs2(int u, int fa)
{
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs2(v, u);
        ans[u] += ans[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    dep[0] = 0;
    dfs(1, 0);
    for (int i = 1; i < n; i++)
    {
        int s = a[i];
        int t = a[i + 1];
        int ft = f[a[i + 1]][0];
        int r = lca(s, t);
        int fr = f[lca(s, t)][0];
        if (r != t)
        {
            ans[s]++;
            ans[ft]++;
            ans[r]--;
            ans[fr]--;
        }
        else
        {
            ans[s]++;
            ans[t]--;
        }
    }
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    cout << "\n";
    return 0;
}