【JLOI2014】松鼠的新家

题面

分析

题目非常好理解，难就难在需要用到的算法，我这个数据结构菜鸟一开始直接打了个LCA（因为树剖不会写），t掉了......只有(50pts)。现在暂时还只有这个代码.......

代码

50pts:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#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 <typename T> 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,1);
    cnt[visit[1]]++;
    go(1);
    for (int i = 1; i <= n; ++i) printf("%dn",cnt[i]);
    return 0;
}