洛谷P3258 [JLOI2014]松鼠的新家

\(\Large\textbf{Description: } \large{一棵树，给出一个游历顺序，每次经过一点一次，此点点权加1，最后一个点不用再加，输出所有点的点权。}\)

\(\Large\textbf{Solution: } \large{很明显的树上点差分，注意一下细节即可。\\觉得这道题属实水，谈一下带给我的启发吧。记得有这么一句话 \text{Think twice, code once.}\\一开始码完有个细节没注意，然后看了一下标签，线段树？？当时就怀疑自己想假了，但是后来仔细想想没问题，改了下细节就A了。\\总之，以后码前先仔细想清楚自己算法的正确性，别半路醒悟；而且事先想好一些细节处理，代码一气呵成。}\)

\(\Large\textbf{Code: }\)

#include <cstdio>
#include <algorithm>
#define LL long long
#define gc() getchar()
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
using namespace std;
const int N = 3e5 + 5;
int n, cnt, head[N], top[N], f[N], dep[N], dir[N], son[N], size[N], ans[N];

struct Edge {
    int to, next;   
}e[N << 1];

inline int read() {
    char ch = gc();
    int ans = 0;
    while (ch > '9' || ch < '0') ch = gc();
    while (ch >= '0' && ch <= '9') ans = (ans << 1) + (ans << 3) + ch - '0', ch = gc();
    return ans;
}

inline void add(int x, int y) {
    e[++cnt].to = y;
    e[cnt].next = head[x];
    head[x] = cnt;  
}

inline void dfs1(int x, int fa) {
    int Max = 0;
    f[x] = fa;
    size[x] = 1;
    dep[x] = dep[fa] + 1;
    for (int i = head[x]; i ; i = e[i].next) {
        int u = e[i].to;
        if (u == fa) continue;
        dfs1(u, x);
        size[x] += size[u];
        if (size[u] > Max) Max = size[u], son[x] = u;
    }
}

inline void dfs2(int x, int tp) {
    top[x] = tp;
    if (!son[x]) return;
    dfs2(son[x], tp);
    for (int i = head[x]; i ; i = e[i].next) {
        int u = e[i].to;
        if (u == son[x] || u == f[x]) continue;
        dfs2(u, u);
    }
}

inline int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }   
    return dep[x] < dep[y] ? x : y;
}

inline void modify(int x, int y) {
    int lca = LCA(x, y);
    ++ans[y], ++ans[x], --ans[lca], --ans[f[lca]];
}

inline void dfs(int x, int fa) {
    for (int i = head[x]; i ; i = e[i].next) {
        int u = e[i].to;
        if (u == fa) continue;
        dfs(u, x);
        ans[x] += ans[u];
    }   
}

int main() {
    n = read();
    int x, y;
    rep(i, 1, n) dir[i] = read(); 
    rep(i, 2, n) x = read(), y = read(), add(x, y), add(y, x);
    dfs1(1, 0); 
    dfs2(1, 1);
    rep(i, 2, n) modify(dir[i - 1], dir[i]);
    dfs(1, 0);
    rep(i, 1, n) {
        if (i == dir[1]) printf("%d\n", ans[i]);
        else printf("%d\n", ans[i] - 1);
    }
    return 0;
} 

洛谷P3258 [JLOI2014]松鼠的新家

原文：https://www.cnblogs.com/Miraclys/p/12419624.html