【JLOI2014】松鼠的新家

概述题面 分析 题目非常好理解，难就难在需要用到的算法，我这个数据结构菜鸟一开始直接打了个LCA（因为树剖不会写），t掉了......只有\(50pts\)。现在暂时还只有这个代码....... 代码 50pts: #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define il inlin

题面

分析

题目非常好理解，难就难在需要用到的算法，我这个数据结构菜鸟一开始直接打了个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("%d\n",cnt[i]);    return 0;}

总结

以上是内存溢出为你收集整理的【JLOI2014】松鼠的新家全部内容，希望文章能够帮你解决【JLOI2014】松鼠的新家所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。