【Luogu P3258】[JLOI2014]松鼠的新家

Luogu P3258

题意就是对于一棵树，要求按照给出的顺序对每一个节点进行访问，记录每一个节点被经过的次数；特别地，我们认为只有从一个节点往外走才能被认为是经过一次。（最后一句话非常重要，仔细理解题意）

前置知识：树链剖分，差分。

最开始看到这道题我是打算使用树链剖分+线段树来做的。

但是我发现这个答案只需要每一个房间的糖果数……也就是说只需要区间修改+单点查询。

如果使用线段树的话，可能造成大量的空间浪费，而且常数也不小。

所以，我选择了使用树链剖分+差分进行统计。

由于差分写得比较少，本人卡了好一会。

大致思路如下：对于\(a[i-1]\)和\(a[i]\)两个节点，利用树链剖分求出两者之间的路径。

其实就是树剖求\(LCA\),每次比较两点的链头深度，深度大的往上跳，直至两点位于同一重链上。

把经过的每一个点权\(+1\)，终点会被重复统计，所以每一次处理完毕都要让终点\(-1\)。

#include<cstdio>

#include<algorithm>

using namespace std;

struct data

{

    int to,next;

}e[600005];

int head[300005],cnt,size[300005],fa[300005],d[300005],top[300005];

int a[300005],ans[3000005],id[300005],tim,wson[300005],n;

void add(int u,int v)

{

    e[++cnt].to=v;

    e[cnt].next=head[u];

    head[u]=cnt;

}

void dfs1(int u,int f,int de)

{

    size[u]=1;

    fa[u]=f;

    d[u]=de;

    for (int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if (v==f) continue;

        dfs1(v,u,de+1);

        size[u]+=size[v];

        if (size[wson[u]]<size[v]) wson[u]=v;

    }

}

void dfs2(int u,int t)

{

    top[u]=t;

    id[u]=++tim;

    if (wson[u]) dfs2(wson[u],t);

    for (int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

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

        dfs2(v,v);

    }

}

void lca(int x,int y)

{

    if (d[top[x]]<d[top[y]]) swap(x,y);

    while (top[x]!=top[y])

    {

        if (d[top[x]]<d[top[y]]) swap(x,y);

        ans[id[top[x]]]+=1;ans[id[x]+1]-=1;

        x=fa[top[x]];

    }

    if (d[x]<d[y]) swap(x,y);

    ans[id[y]]+=1;ans[id[x]+1]-=1;

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&a[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,1);

    dfs2(1,1);

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

    {

        lca(a[i],a[i-1]);

        ans[id[a[i]]]--;

        ans[id[a[i]]+1]++;

        //注意dfs序和原编号的映射关系

    }

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

        ans[i]+=ans[i-1];//用差分数组求出答案数组

    for (int i=1;i<=n;i++) printf("%d\n",ans[id[i]]);

    return 0;

}

巴特西

【Luogu P3258】[JLOI2014]松鼠的新家

最新文章

热门文章