洛谷 P3237 [HNOI2014]米特运输 题解【树】【哈希】
点击量：301
题目描述
米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。
D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通道连接起来，构成一棵以1号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为0，属于第1层；根结点的子节点深度为1，属于第2层；依此类推，深度为i的结点属于第i+1层。
建好高速通道之后，D星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第i个城市建有一个容量为A[i]的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。
如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。
早上六点到七点间，根节点城市（1号城市）会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特，它只接受子节点传输来的米特。
早上七点，城市之间启动米特传输过程，传输过程逐层递进：先是第2层节点城市向第1层（根节点城市，即1号城市）传输，直到第1层的储存器满或第2层的储存器全为空；然后是第3层向第2层传输，直到对于第2层的每个节点，其储存器满或其子节点（位于第3层）的储存器全为空；依此类推，直到最后一层传输完成。传输过程一定会在晚上六点前完成。
由于技术原因，运输方案需要满足以下条件：
(1)不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态，这个时候储存器仍然会启动自动收集米特的程序，而给已经储存有米特的储存器启动收集程序可能导致危险，也就是说要让储存器到了晚上六点时要么空要么满；
(2)关于首都——即1号城市的特殊情况， 每天早上六点到七点间1号城市中的米特储存器里的米特会自动被消耗殆尽，即运输方案不需要考虑首都的米特怎么运走；
(3)除了1号城市，每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点，不允许储存器中残存的米特与外来的米特发生混合；
(4)运向某一个城市的若干个来源的米特数量必须完全相同，不然，这些来源不同的米特按不同比例混合之后可能发生危险。
现在D星人已经建立好高速通道，每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件，可能需要重建一些城市中的米特储存器。你可以，也只能，将某一座城市（包括首都）中原来存在的米特储存器摧毁，再新建一座任意容量的新的米特储存器，其容量可以是小数（在输入数据中，储存器原始容量是正整数，但重建后可以是小数），不能是负数或零，使得需要被重建的米特储存器的数目尽量少。
输入输出格式
输入格式：
第一行是一个正整数N，表示城市的数目。 接下来N行，每行一个正整数，其中的第i行表示第i个城市原来存在的米特储存器的容量。 再接下来是N-1行，每行两个正整数a，b表示城市b到城市a有一条高速通道(a≠b)。
输出格式：
输出文件仅包含一行，一个整数，表示最少的被重建（即修改储存器容量）的米特储存器的数目。
输入输出样例
输入样例#1：5543211 21 32 42 5输出样例#1：3说明
【样例解释】
一个最优解是将A[1]改成8，A[3]改成4，A[5]改成2。这样，2和3运给1的量相等，4和5运
给2的量相等，且每天晚上六点的时候，1，2满，3，4，5空，满足所有限制条件。
对于100%的数据满足N<500000，A[j]<10^8
题目除了比较长，也就比较难吧
总结一下就是两句话：①一个节点的所有儿子的存储量相等；②该节点的存储量等于所有儿子之和。（③ 1号城市为根节点）
我们需要做的就是找到根节点的一个最优存储量，使得树上所有节点的容量改变的次数最少而符合要求，所以我们要选择树上所有点各作一次基准点，也就是让这个基准点的存储量维持不变，通过这个基准点将树上所有点都修改为符合要求的量。找出这些量与原存储量相差的个数最小的方案。
我们从总结知道，根节点的存储量一旦确定，整棵树的存储量也就确定了。
举个例子，
这时 我们如果取1作为基准点，那么1不变，树会变成这样（蓝色为修改后）
就需要改变7个节点。
而取2或5为基准点，结果都是
我们则认为它们是等价的，这样更优，只需要修改6个节点。
这时，我们就有了$ O(N^2)$的做法：枚举基准点并进行比对，与原存储量相同的越多越好。
事实上，我们不用枚举基准点，从上面的分析我们可以看出，如果在两种情况中一个点的存储量相同，那么这两种情况等价。从这里出发我们就有了一种更优的算法：在DFS过程中，对于每个点计算它到根节点1的倍数关系（所谓倍数关系就是上图中 5与2是3倍，2与1是3倍，8与4是1倍，8与1是3倍 等）。从上到下，把已经计算的倍数带入DFS函数中，就可以计算出遍历到当前节点时，如果当前节点不改动，1号节点的存储量是多少了，设这个存储量为$ k$，我们用桶将$ k$的下标+1。那么每当1号节点的存储量计算出$ k$时，将桶的$ k$下标+1，这样，桶里存的就是当1号节点存储量为$ k$时，与这个状态等价的状态个数了。由上面我们可知的是：如果有某种条件推出$ k$，而这个条件是由某个子节点推出来的，那么这个子节点和根节点的存储量等价，所以当根节点存储量为$ k$时，这个子节点是不用改变的，所以等价的越多，需要修改的就越少，最终的答案就是(设$ k$为最优解)$ n-b[k]$。时间复杂度为$ O(N)$。
重点是，A[i]最大是$ 10^8$，A[1]最极端情况可以达到叶子节点个数$ m\times max(A[i])$ 而在最极端的情况下，会有$ 499999(\approx 500000)$个叶子，那么A[1]就最大约有$ 10^{13}$。虽说我们可以开long long存数字，但是不能通过下标访问啊。这样就必须离散了（在最大值难以估计时，也可以用$ ln a+ln b=ln a\times b$来防止爆long long)。
$ tips:luogu$的数据hash时 mod 1000007会卡一组数据，mod maxint（自动溢出）只能拿一半的分。三分脸注定，七分看命题人啊。。。///不要学我取的大质数，评测记录显示我的内存卡到了123MB。。。
- 错误笔记：每做一次乘法都要mod上那个常数，不然桶开得只有那么大，会RE的。。。
Code：
#include<cstdio>
#include<cstring>
#define wys 19260817
int bu[19260822];//存储用的桶
struct node//链表
{
int n;
node *nxt;
node(int n)
{
this->n=n;
nxt=NULL;
}
node(){nxt=NULL;}
};
node head[500800],*tail[500080];
long long a[500800];//原始存储量
int son[500800];//用儿子个数来表示儿子与自己的倍数关系
bool used[500800];
void Dfs(int x)//遍历找出倍数关系（儿子个数）
{
node *p=&head[x];//son[]已初始化为0
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
son[x]++;
used[p->n]=true;
Dfs(p->n);
used[p->n]=false;
}
}
void dfs(int x,long long index)//x是当前遍历到的点，index是目前的倍数关系
{
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])
continue;
used[p->n]=true;
dfs(p->n,(long long)index*son[x]%wys);//一定要在传入数据时mod
used[p->n]=false;
}
bu[(long long)(index*a[x])%wys]++;//随机访问时也一定要mod
}
int main()
{
int n,u,v;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
tail[i]=&head[i];
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
tail[u]->nxt=new node(v);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u);
tail[v]=tail[v]->nxt;
}
memset(used,0,sizeof(used));
memset(son,0,sizeof(son));
memset(bu,0,sizeof(bu));
used[1]=true;
Dfs(1);
memset(used,0,sizeof(used));
used[1]=true;
dfs(1,1);
int maxx=0,tmp;
for(int i=0;i<=19260816;i++)//找最多等价次数
if(bu[i]>maxx)
{
maxx=bu[i];
tmp=i;
}
printf("%d\n",n-maxx);
return 0;
}
说点什么