BZOJ 3631: [JLOI2014]松鼠的新家树上差分 + LCA

Description

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。

可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。

现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

Input

第一行一个整数n，表示房间个数

第二行n个整数，依次描述a1-an

接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

Output

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

题解：

树剖 + 线段树显然是可以的.
不过可以用更加简单的树上查分.
对于 $<u,c,v>$ ($c$ 为 $lca(u,v)$)
只需对于 $u,v$ 加上差值， $c$ 与 $fa[c]$上减掉差值即可.
注意：每次要将除了 $1$ 以外其他所有点的点权都减 1.
因为上述方法会把中转点算两次

Code:

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 300001

using namespace std;

int hd[maxn], to[maxn<<1], nex[maxn<<1], fa[maxn], siz[maxn], top[maxn], hson[maxn],len[maxn],arr[maxn],buck[maxn];

int edges;

int ans[maxn];

void add(int u,int v)

{

    nex[++edges]=hd[u], hd[u]=edges, to[edges]=v;

}

void dfs1(int u,int ff)

{

    fa[u] = ff, siz[u] = 1, len[u] = len[ff] + 1;

    for(int i=hd[u];i;i=nex[i])

    {

        int v=to[i];

        if(v==ff) continue;

        dfs1(v,u);

        siz[u] += siz[v];

        if(siz[v] > siz[hson[u]]) hson[u] = v;

    }

}

void dfs2(int u,int tp)

{

    top[u]=tp;

    if(hson[u]) dfs2(hson[u], tp);

    for(int i=hd[u];i;i=nex[i])

    {

        int v=to[i];

        if(v==fa[u] || v==hson[u]) continue;

        dfs2(v, v);

    }

}

int lca(int a,int b)

{

    while(top[a] ^ top[b]) len[top[a]] < len[top[b]] ? b = fa[top[b]] : a = fa[top[a]];

    return len[a] > len[b] ? b : a;

}

void dfs(int u)

{

    for(int i=hd[u];i;i=nex[i])

    {

        int v=to[i];

        if(v==fa[u]) continue;

        dfs(v);

        buck[u]+=buck[v];

    }

}

int main()

{

    // setIO("input");

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;++i) scanf("%d",&arr[i]);

    for(int i=1;i<n;++i)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v), add(v,u);

    }

    dfs1(1,0);

    dfs2(1,1);

    for(int i=2;i<=n;++i)

    {

        int c = lca(arr[i], arr[i-1]);

        ++buck[arr[i]];

        ++buck[arr[i-1]];

        --buck[c];

        --buck[fa[c]];

    }

    dfs(1);

    for(int i=2;i<=n;++i) --buck[arr[i]];

    for(int i=1;i<=n;++i)

    {

        printf("%d\n",buck[i]);

    }

    return 0;

}

巴特西

BZOJ 3631: [JLOI2014]松鼠的新家树上差分 + LCA

Description

Input

Output

题解：

最新文章

热门文章

巴特西

BZOJ 3631: [JLOI2014]松鼠的新家 树上差分 + LCA

Description

Input

Output

题解：

最新文章

热门文章

BZOJ 3631: [JLOI2014]松鼠的新家树上差分 + LCA