BZOJ_3573_[Hnoi2014]米特运输_树形DP+hash

BZOJ_3573_[Hnoi2014]米特运输_树形DP+hash

题意：

给你一棵树每个点有一个权值，要求修改最少的权值，使得每个节点的权值等于其儿子的权值和且儿子的权值都相等。

分析：

首先我们发现在树中如果确定一个点的权值，那么整颗树的方案就能够确定

问题转化成求哪个方案包含的点最多

如何求包含这个点的是哪个方案？

可以给每个点分配一个新的权值

不妨假设1号点的权值不变

1号点的儿子的权值为原来的权值乘上1号点儿子的个数.......以此类推。

发现权值相同的点在一个方案里

由于权值可能很大，我们随缘取模哈希一下就行

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define LL long long

#define N 500050

int head[N],to[N<<1],nxt[N<<1],val[N],cnt;

int n,son[N],dep[N];

LL now[N];

int h[1930010],p=1910009;

int ans,key[1930010];

inline void add(int u,int v)

{

    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

}

void insert(LL x)

{

    int k=(x%p+p)%p;

    while(h[k]&&key[k]!=x)

    {

        k++;

    }

    h[k]++;key[k]=x;

    ans=max(ans,h[k]);

}

void dfs(int x,int y)

{

    int i;

    for(i=head[x];i;i=nxt[i])

    {

        if(to[i]!=y)

        {

            son[x]++;

        }

    }

    for(i=head[x];i;i=nxt[i])

    {

        if(to[i]!=y)

        {

            now[to[i]]=now[x]*son[x]%p;

            insert(val[to[i]]*now[to[i]]%p);

            dfs(to[i],x);

        }

    }

}

int main()

{

    scanf("%d",&n);

    int i,x,y;

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

    {

        scanf("%d",&val[i]);

    }

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

    {

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    insert(val[1]);

    now[1]=1;

    dfs(1,0);

    printf("%d\n",n-ans);

}