[BZOJ1782][Usaco2010 Feb]slowdown 慢慢游

1782: [Usaco2010 Feb]slowdown 慢慢游

Time Limit: 1 Sec Memory Limit: 64 MB Submit: 770 Solved: 494 [Submit][Status][Discuss]

Description

每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放慢自己的速度，防止打扰他的朋友。考虑如下的牧场结构（括号内的数字代表了牧场的所有者）。

Input

* 第1行 : 一个正整数N * 第2…N行: 第i+1行包括一对正整数A_i,B_i * 第N+1..N+N行: 第 N+i行包括一个正整数: P_i

Output

* 第一行到第N行：第i行表示第i只奶牛需要被放慢的次数

Sample Input

5
1 4
5 4
1 3
2 4
4
2
1
5
3

Sample Output

0
1
0
2
1

链剖 + 线段树

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
char buf[10000000], *ptr = buf - 1;
inline int readint(){
    int f = 1, n = 0;
    char ch = *++ptr;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = *++ptr;
    }
    while(ch <= '9' && ch >= '0'){
        n = (n << 1) + (n << 3) + ch - '0';
        ch = *++ptr;
    }
    return f * n;
}
const int maxn = 100000 + 10;
struct Edge{
    int to, next;
    Edge(){}
    Edge(int _t, int _n): to(_t), next(_n){} 
}e[maxn * 2];
int fir[maxn] = {0}, cnt = 0;
inline void ins(int u, int v){
    e[++cnt] = Edge(v, fir[u]); fir[u] = cnt;
    e[++cnt] = Edge(u, fir[v]); fir[v] = cnt;
}
int fa[maxn], dep[maxn], siz[maxn], son[maxn];
void dfs1(int u){
    son[u] = 0;
    siz[u] = 1;
    for(int v, i = fir[u]; i; i = e[i].next){
        v = e[i].to;
        if(v == fa[u]) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]]) son[u] = v;
    }
}
int top[maxn], ref[maxn], tcnt = 0;
void dfs2(int u){
    ref[u] = ++tcnt;
    if(!son[u]) return;
    top[son[u]] = top[u];
    dfs2(son[u]);
    for(int v, i = fir[u]; i; i = e[i].next){
        v = e[i].to;
        if(v == fa[u] || v == son[u]) continue;
        top[v] = v;
        dfs2(v);
    }
}
int n;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
int sum[maxn << 2] = {0};
void Update(int qw, int l, int r, int rt){
    sum[rt]++;
    if(l == r) return;
    else{
        int mid = l + r >> 1;
        if(qw <= mid) Update(qw, lson);
        else Update(qw, rson);
    }
}
int Query(int ql, int qr, int l, int r, int rt){
    if(ql <= l && r <= qr) return sum[rt];
    else{
        int mid = l + r >> 1, ret = 0;
        if(ql <= mid) ret += Query(ql, qr, lson);
        if(qr > mid) ret += Query(ql, qr, rson);
        return ret;
    }
}
inline void solve(int x){
    int ans = 0;
    while(top[x] != 1){
        ans += Query(ref[top[x]], ref[x], 1, n, 1);
        x = fa[top[x]];
    }
    ans += Query(ref[1], ref[x], 1, n, 1);
    printf("%d
", ans);
}
int main(){
    fread(buf, sizeof(char), sizeof(buf), stdin);
    n = readint();
    for(int i = 1; i < n; i++) ins(readint(), readint());
    fa[1] = 0;
    dfs1(1);
    top[1] = 1;
    dfs2(1);
    for(int p, i = 1; i <= n; i++){
        p = readint();
        solve(p);
        Update(ref[p], 1, n, 1);
    }
    return 0;
}