P3258题解

__vector__ · 2022-06-11 10:36:02 · 个人记录

做法

使用差分来做，设 cf_i 表示 i 点到根节点的路径上每一个点加上 cf_i。这样对于 u \rightarrow t 的路径上每一个点加一，处理方式如下：

这是十分显然的。然后 dfs 处理出每个点的值大小即可
另外，由于每个 a_i (i \in [2,n-1])都算了两次（既做过起点又做过终点），所以这些点要减去 1，对于 a_n，因为这个点不需要作为终点单独放置糖，但是计算的时候它被作为终点算了一次，所以也要减去 1。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=3e5+5;
    int a[maxn];
    int n;
    int head[maxn<<1];
    ll cf[maxn];
    struct EDGE
    {
        int to,nxt;
    }edge[maxn<<1];
    int cnt;
    inline void add(int u,int to)
    {
        edge[++cnt].to=to;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int dep[maxn];
    int father[maxn][31];
    void dfs(int u,int fa)
    {
        dep[u]=dep[fa]+1;
        father[u][0]=fa;
        for(int i=1;i<=30;i++)
        {
            father[u][i]=father[father[u][i-1]][i-1];
        }
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==fa)continue;
            dfs(to,u);
        }
    }
    inline int lca(int a,int b)
    {
        if(dep[a]<dep[b])swap(a,b);
        for(int i=30;i>=0;i--)
        {
            if(dep[father[a][i]]>=dep[b])
            {
                a=father[a][i];
            }
        }
        if(a==b)return a;
        for(int i=30;i>=0;i--)
        {
            if(father[a][i]!=father[b][i])
            {
                a=father[a][i];
                b=father[b][i];
            }
        }
        return father[a][0];
    }
    void dfs2(int u,int fa)
    {
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==fa)continue;
            dfs2(to,u);
            cf[u]+=cf[to];
        }
    }
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int x,y;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        dfs(1,0);
        for(int i=1;i<n;i++)
        {
            int as=a[i],bs=a[i+1];
            int _lca=lca(as,bs);
            cf[as]++;
            cf[bs]++;
            cf[_lca]--;
            cf[father[_lca][0]]--;
        }
        dfs2(1,0);
        for(int i=2;i<=n;i++)
        {
            cf[a[i]]--;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%lld\n",cf[i]);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}