洛谷P3237 [HNOI2014]米特运输

 

 题干真长

思路分析：

　　当我们把样例画出来后，我们发现，我们只要确定一个点的权值，那么这棵树所有点的权值就已知了，例如，我们设2号节点权值已知且为2，那么我们依据题意想要让他符合要求必须有5,4号节点权值为1；3号节点权值为2；1号节点权值为4。

所以我们可以枚举树上的所有的点，求出该节点不动时根节点（即1号）的权值，如果两个不同节点不动时根节点值相同，那么他们一定是隶属于相同的一棵树的（这相当于根节点确定，子节点都相应确定），我们求出每一种情况后对节点数减去相同数取最小值即可（因为我们确定一个节点后所建的树一定是符合要求的，相同数即为不用动的点）。

在计算根节点过程中由于我们要不断地乘（因为根节点权值一定是所有树上除根节点外结点的权值总和，可以根据上图模拟一下），如果硬乘会爆long long，所以我们可以对乘法的每一项取log，可将乘法转化为加法，但注意在判等时应该是他们两个的差小于1e-6，注意精度。

上代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
const double jingdu=1e-6;  //精度用于判等 
int n,Head[N],tot,out[N];
int capacity[N]; //表示容量,capacity是容量的英文 
struct Node{
    int next,to;
}e[N];
void Add(int x,int y){
    e[++tot].to=y;
    e[tot].next=Head[x];
    Head[x]=tot;
}
double val[N];  //可能是小数用double 
void dfs(int x,int fa,double ans){
    val[x]=ans+log(capacity[x]);  //递归,求出每个点不动时根节点的权值. 
    out[x]--;            //注意这里的加法实际上是乘法,因为用到了log,out--是减去父亲的那条边 
    for(int i=Head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,x,ans+log(out[x]));
    }
}
int Max=0,sum=1;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&capacity[i]);
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        Add(y,x);Add(x,y);out[x]++;out[y]++; //记录出度 
    }
    out[1]++,dfs(1,0,0);//根节点本不应该--,这里先给它加上 
    sort(val+1,val+1+n);//小技巧判等数量 
    for(int i=2;i<=n;++i){
        if(val[i]-val[i-1]<jingdu) sum++;
        else Max=max(Max,sum),sum=1;
    }
    printf("%d
",n-Max);
    return 0;
}