[BZOJ3573]米特运输 树形DP


原题链接
给一棵点权树,要求你修改最少数量的点的权值,使得最后每个点权值等于其儿子的权值和,且其儿子的权值全相等.
要求修改最少,其实就是使不用修改的最多.容易发现如果钦定一个点的值则可以确定整棵树的值,我们分别钦定每个点不变,求一下根节点的值,设这个值是f[i]那么所有f[i]相等的点就可以同时不变,也就是求出现次数最多的f[i].
注意f[i]会很大,取个log就行了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 502333
using namespace std;
typedef long long ll;
const int mod=1000000007;
inline ll quick_pow(ll x,ll y)
{
    ll re=1;
    for(;y;y>>=1)
    {
        if(y&1)re=re*x%mod;
        x=x*x%mod;
    }
    return re;
}
inline ll inv(ll x)
{
    return quick_pow(x,mod-2);
}
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,head[N],to[N<<1],nxt[N<<1],tot;
inline void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int son[N],a[N];
ll val[N],sum[N];
void dfs(int x,int pre)
{
    int i,y;
    for(i=head[x];i;i=nxt[i])if(to[i]!=pre)son[x]++;
    for(i=head[x];i;i=nxt[i])if((y=to[i])!=pre)
    {
        sum[y]=(sum[x]*son[x])%mod;
        val[y]=(sum[y]*a[y])%mod;
        dfs(y,x);
    }
}
int main()
{
    read(n);
    int i,x,y;
    for(i=1;i<=n;++i)read(a[i]);
    for(i=1;i<n;++i)
    {
        read(x),read(y);
        add(x,y),add(y,x);
    }
    val[1]=a[1],sum[1]=1;
    dfs(1,0);
    sort(val+1,val+n+1);
    int now=1,ans=1;
    for(i=2;i<=n;++i)
    {
        if(val[i]!=val[i-1])now=1;
        else now++;
        ans=max(ans,now);
    }
    cout<<n-ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注