「JLOI 2014」松鼠的新家

发表于 | | 阅读次数:
字数统计: 726 字

Description

题目链接：BZOJ 3631

松鼠的新家新家有 $n$ 个房间，并且有 $n-1$ 根树枝连接，每个房间都可以相互到达。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序：按照 $a_1,a_2\cdots a_n$ 的房间顺序去参观新家，并且每走到一个房间，他就可以从房间拿一块糖果吃。因为松鼠参观指南上的最后一个房间 $a_n$ ，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

数据范围：$2\le n\le 3\times 10^5$

Solution

对于这种树上链增加相同值的问题，都可以使用树上差分来解决。具体的树上差分过程不再赘述，这里主要分析一下这题的细节注意。

首先这是链上点增加 $1$ 的权值的问题，我们可以用标准的点差分。但是我们注意到，每个 $a_i(1< i<n)$，我们在以 $a_i$ 为终点的链（之前的链）和以 $a_i$ 为起点的链（之后的链）都增加了一次，因此我们最后要减去一个 $1$；对于 $a_n$，按照题意这个点作为最后的点不需要放置糖果，也需要减去 $1$。那么我对所有的 $a_i(1<i\le n)$ 在最后都要减去一个 $1$。

时间复杂度：$O(n\log n)$

Code

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
 
#include <cstdio>

const int N=3e5+5,6e5+5;
int n,tot,a[N],dep[N],f[N][21],lnk[N],ter[M],nxt[M],c[N];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=1;(1<<i)<=dep[u];++i) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=lnk[u];i;i=nxt[i]) if(ter[i]^fa) dfs(ter[i],u);
}
int lca(int x,int y) {
    if(dep[x]>dep[y]) x^=y^=x^=y;
    for(int i=20;i>=0;--i) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
    if(x==y) return x;
    for(int i=20;i>=0;--i) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void solve(int u,int fa) {
    for(int i=lnk[u];i;i=nxt[i]) {
        if(ter[i]^fa) solve(ter[i],u),c[u]+=c[ter[i]];
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int u,v,i=1;i<n;++i) {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<n;++i) {
        int p=lca(a[i],a[i+1]);
        ++c[a[i]],++c[a[i+1]],--c[p],--c[f[p][0]];
    }
    solve(1,0);
    for(int i=2;i<=n;++i) --c[a[i]];
    for(int i=1;i<=n;++i) printf("%d\n",c[i]);
    return 0;
}
0%