Luogu3258 - [JLOI2014]松鼠的新家

2017/10/18

题目

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达, 且俩个房间之间的路线都是唯一的。天哪,他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去 A1,再去 A2, ……,最后到 An ,去参观新家。可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他, 每走到一个房间,他就可以从房间拿一块糖果吃。

维尼是个馋家伙,立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间 An 是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

2<= N <= 300000

代码

SB 选手看到题目准备写个树链剖分(数据结构写傻),事实上这道题跟 天天爱跑步 类似,直接树上差分就行了。

注意到每次行走并不包括终点,因此对于每个 u -> v 可以转化成差分标记 Mrk[u]++, Mrk[fa[v]]++, Mrk[lca]--, Mrk[fa[lca]]--

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long LL;
const int SIZ = 6e5 + 1007;
const int M = 22;

struct tgno {
    int v; tgno *n;
} POOL[SIZ], *Head[SIZ]; int ppos;

void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v) { _add(u, v), _add(v, u); }

int N;
int Seq[SIZ];

int dep[SIZ];
int fa[SIZ][M];
void dfs1(int u, int pre = 0, int d = 1) {
    typedef tgno* It;
    
    dep[u] = d;
    fa[u][0] = pre;
    for(int i=1;i<M;i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    
    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre) {
            dfs1(i->v, u, d+1);
        }
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) swap(a, b);
    
    for(int i=M-1;dep[a] < dep[b] && i>=0;i--) {
        if(dep[fa[b][i]] >= dep[a]) b = fa[b][i];
    }
    
    assert(dep[a] == dep[b]);
    
    if(a == b) return a;
    
    for(int i=M-1;fa[a][0] ^ fa[b][0] && i>=0;i--) {
        if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    }
    
    assert(fa[a][0] == fa[b][0]);
    
    return fa[a][0];
}

int mrk[SIZ];
int sav[SIZ], ans[SIZ]; LL sum;
void dfs2(int u, int pre = 0) {
    typedef tgno* It;
    
    sav[u] = sum;
    sum += mrk[u];
    
    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre) {
            dfs2(i->v, u);
        }
    }
    
    ans[u] = int(sum - sav[u]);
}

int main() {
    scanf("%d", &N);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &Seq[i]);
    }
    
    int u, v;
    for(int i=1;i<N;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    
    dfs1(1);
    
    for(int i=1;i<N;i++) {
        int u = Seq[i], v = Seq[i+1], l = lca(u, v);
        mrk[u] += 1;
        mrk[fa[v][0]] += 1;
        mrk[l] -= 1;
        mrk[fa[l][0]] -= 1;
    }
    
    dfs2(1);
    
    for(int i=1;i<=N;i++) {
        printf("%d\n", ans[i]);
    }
}