【HNOI2014】米特运输-题解

题意描述

米特是 $\text{D}$ 星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的 $\text{D}$ 星上，这种米特能源的运输和储存一直是一个大问题。

$\text{D}$星上有$n$个城市，我们将其顺序编号为$1$到$n$，$1$号城市为首都。这$n$个城市由$n-1$条单向高速通道连接起来，构成一棵以$1$号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为$0$，属于第$1$层；根结点的子节点深度为$1$，属于第$2$层；依此类推，深度为$i$的结点属于第$i+l$层。

建好高速通道之后，$\text{D}$星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第$i$个城市建有一个容量为$a_i$的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。

如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。

早上六点到七点间，根节点城市（$1$号城市）会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特，它只接受子节点传输来的米特。

早上七点，城市之间启动米特传输过程，传输过程逐层递进：先是第$2$层节点城市向第$1$层（根节点城市，即$1$号城市）传输，直到第$1$层的储存器满或第$2$层的储存器全为空；然后是第$3$层向第$2$层传输，直到对于第$2$层的每个节点，其储存器满或其予节点（位于第$3$层）的储存器全为空；依此类推，直到最后一层传输完成。传输过程一定会在晚上六点前完成。

由于技术原因，运输方案需要满足以下条件：

不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态，这个时候储存器仍然会启动自动收集米特的程序，而给已经储存有米特的储存器启动收集程序可能导致危险，也就是说要让储存器到了晚上六点时要么空要么满；

关于首都——即$1$号城市的特殊情况， 每天早上六点到七点间$1$号城市中的米特储存器里的米特会自动被消耗殆尽，即运输方案不需要考虑首都的米特怎么运走；

除了$1$号城市，每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点，不允许储存器中残存的米特与外来的米特发生混合；

运向某一个城市的若干个来源的米特数量必须完全相同，不然，这些来源不同的米特按不同比例混合之后可能发生危险。

现在$\text{D}$星人已经建立好高速通道，每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件，可能需要重建一些城市中的米特储存器。你可以，也只能，将某一座城市（包括首都）中原来存在的米特储存器摧毁，再新建一座任意容量的新的米特储存器，其容量可以是小数（在输入数据中，储存器原始容量是正整数，但重建后可以是小数），不能是负数或零，使得需要被重建的米特储存器的数目尽量少。

---

输入格式

第一行是一个正整数$n$，表示城市的数目。

接下来$n$行，每行一个正整数，其中的第$i$行表示第$i$个城市原来存在的米特储存器的容量。

再接下来是$n - 1$行，每行两个正整数$a$，$b$表示城市$b$到城市$a$有一条高速通道。

---

输出格式

输出文件仅包含一行，一个整数，表示最少的被重建（即修改储存器容量）的米特储存器的数目。

---

Input & Output ‘s examples

Input ‘s eg

5
5
4
3
2
1
1 2
1 3
2 4
2 5

Output ‘s eg

3

---

数据范围与约定

对于$100\%$的数据满足$1 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq 10^8$。

保证输入数据中的$a$与$b$不相同。

---

分析

真就tm阅读理解题呗

题意即给你一颗树，需要你改变一些点的点权，使其满足以下性质：

1. 每个点的子节点权值均相同
2. 父节点权值为其各子节点的权值和。

考虑如何计算。仔细观察，不难发现当一个点的点权确定后，整棵树的点权也将随之确定。

设$f[i]$表示$i$节点的权值为$val[i]$时，根节点的权值是$i$节点的几倍。即

$$val[root] = f[i] \times val[i]$$

转移比较简单，为

$$f[to] = f[x] \times (in[x] - 1)$$

其中，$in[x]$表示的是节点$x$的度数(即有多少边与节点$x$相连)。而$in[x] - 1$是因为每个点对答案产生贡献的边为该点与子节点的连边，因此，我们需要减去父节点产生的度数

特别地，对于根节点我们需要特殊处理，即$f[to] = f[1] \times in[x]$。因为根节点没有父亲。

最后对$f$数组进行排序，如果$f[i] = f[j]$则说明$i$与$j$可以同时满足条件，不需要更改。因此只需找出$f$数组中的最长相等序列，然后用总数减掉即可。

但还有最后一个问题：节点点权的范围是$10^8$，直接乘一定会溢出。

对此，我们可以写个高精采用整数哈希或者是利用公式$log(a) + log(b) = log(a \times b)$转换为加法(注意可能产生的精度误差)。

剩下的见代码注释。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 500101;
const int HA = 998244353;
const int INF = 2147483647;
const double eps = 1e-8;
const long long INFL = 9223372036854775807;

int n , num[M] , in[M];

struct Edge{
    int to , last;
}edge[M << 1];

int edge_num;
int head[M << 1];

I void add_edge(int from , int to){
    edge[++ edge_num] = (Edge){to , head[from]}; head[from] = edge_num;
    edge[++ edge_num] = (Edge){from , head[to]}; head[to] = edge_num;
}

double f[M];

void dfs(int x , int fa , double val){
    f[x] = val + log(num[x]);
    in[x] --;   
    //对于答案产生贡献的边为该节点与其子节点的连边，因此需要减去父节点的度数   
    PE(i , x){
        int to = edge[i].to;
        if(to == fa) continue;
        dfs(to , x , val + log(in[x]));
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    scanf("%d" , &n);
    rep(i , 1 , n){
        scanf("%d" , &num[i]);
    }
    int u , v;
    rep(i , 1 , n - 1){
        scanf("%d%d" , &u , &v);
        add_edge(u , v);
        in[u] ++ , in[v] ++;
    }
    in[1] ++;    //1号节点没有父亲，需要单独加一个度数
    dfs(1 , 0 , log(1));
    sort(f + 1 , f + 1 + n);
    int ans = 1 , cnt = 0;
    rep(i , 2 , n){
        if(f[i] - f[i - 1] < eps){  //注意可能存在的精度误差
            cnt ++;
        }
        else{
            ans = max(ans , cnt);
            cnt = 1;
        }
    }
    printf("%d\n" , n - ans);

    return 0;
}

---

THE END