分析
题目非常好理解，难就难在需要用到的算法，我这个数据结构菜鸟一开始直接打了个LCA（因为树剖不会写），t掉了......只有\(50pts\)。现在暂时还只有这个代码.......
\(\uparrow\)当我SB\(\uparrow\)
正确做法：LCA+倍增优化+树上差分
代码
50pts:
#include#include #include #include #define il inline#define re register#define maxn 300005#define tie0 cin.tie(0),cout.tie(0)#define fastio ios::sync_with_stdio(false)#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)using namespace std;typedef long long ll;template inline void read(T &x) { T f = 1; x = 0; char c; for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1; for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); x *= f;}struct edge { int to, nxt;}e[maxn<<1];int n;int tot, head[maxn<<1];int visit[maxn], cnt[maxn], fa[maxn], dep[maxn];void addedge(int u, int v) { e[++tot].to = v, e[tot].nxt = head[u], head[u] = tot;}void dfs(int u, int _fa, int dpt) { fa[u] = _fa; dep[u] = dpt; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == _fa) continue; dfs(v, u, dpt + 1); }}void LCA(int s, int t) { if (t != visit[n]) cnt[t]++; if (dep[s] > dep[t]) swap(s, t); while (dep[s] < dep[t]) { t = fa[t]; if (t != s) cnt[t]++; } while (s != t) { s = fa[s], t = fa[t]; if (s == t) cnt[s]++; else cnt[s]++, cnt[t]++; }}void go(int i) { if (i == n) return; LCA(visit[i], visit[i+1]); go(i + 1);}int main() { read(n); for (int i = 1; i <= n; ++i) read(visit[i]); int u, v; for (int i = 1; i < n; ++i) { read(u), read(v); addedge(u, v); addedge(v, u); } dfs(1, 0, 1); cnt[visit[1]]++; go(1); for (int i = 1; i <= n; ++i) printf("%d\n",cnt[i]); return 0;}
100pts:
#include#include #include #include #include #define il inline#define re register#define maxn 300005#define tie0 cin.tie(0),cout.tie(0)#define fastio ios::sync_with_stdio(false)#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)using namespace std;typedef long long ll;template inline void read(T &x) { T f = 1; x = 0; char c; for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1; for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); x *= f;}struct edge { int to, nxt;}e[maxn<<1];int n, logn;int cnt = 1, head[maxn<<1];int visit[maxn], fa[maxn][21], dep[maxn], f[maxn], c[maxn];void addedge(int u, int v) { e[++cnt].to = v, e[cnt].nxt = head[u], head[u] = cnt;}void dfs(int u, int _fa, int dpt) { fa[u][0] = _fa; dep[u] = dpt; for (int i = 1; i <= logn; ++i) fa[u][i] = fa[fa[u][i-1]][i-1]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == _fa) continue; dfs(v, u, dpt + 1); }}void LCA(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int x = u, y = v; while (dep[u] > dep[v]) { for (int i = logn; i >= 0; --i) { if (dep[fa[u][i]] > dep[v]) u = fa[u][i]; } u = fa[u][0]; } if (v == u) { c[fa[u][0]]--; c[x]++; return; } for (int i = logn; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; u = fa[u][0]; c[u]--, c[fa[u][0]]--; c[x]++, c[y]++;}void get_ans(int u) { f[u] = c[u]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == fa[u][0]) continue; get_ans(v); f[u] += f[v]; }}void solve() { for (int i = 1; i < n; ++i) LCA(visit[i], visit[i + 1]); get_ans(visit[1]); for (int i = 1; i <= n; ++i) { if (i == visit[1]) printf("%d\n", f[i]); else printf("%d\n", f[i] - 1); }}int main() {// File("testdata"); read(n); while ((1 << logn) < n) logn++; for (int i = 1; i <= n; ++i) read(visit[i]); int u, v; for (int i = 1; i < n; ++i) { read(u), read(v); addedge(u, v); addedge(v, u); } addedge(0, visit[1]); dfs(0, 0, 1); solve(); return 0;}