Luogu3576 POI2014 MRO-Ant colony 【树形DP】*
Luogu3576 POI2014 MRO-Ant colony
The ants are scavenging an abandoned ant hill in search of food.
The ant hill has nn chambers and n-1n−1 corridors connecting them.
We know that each chamber can be reached via a unique path from every other chamber.
In other words, the chambers and the corridors form a tree.
There is an entrance to the ant hill in every chamber with only one corridor leading into (or out of) it.
At each entry, there are gg groups ofants respectively.
These groups will enter the ant hill one after another, each successive group entering once there are no ants inside.
Inside the hill, the ants explore it in the following way:
Upon entering a chamber with dd outgoing corridors yet unexplored by the group,the group divides into dd groups of equal size. Each newly created group follows one of the d corridors.If d=0 , then the group exits the ant hill.
If the ants cannot divide into equal groups, then the stronger ants eat the weaker until a perfect division is possible.Note that such a division is always possible since eventually the number of ants drops down to zero.Nothing can stop the ants from allowing divisibility - in particular, an ant can eat itself, and the last one remaining will do so if the group is smaller than dd .
The following figure depicts mm ants upon entering a chamber with three outgoing unexplored corridors, dividing themselves into three (equal) groups of ants each.
A hungry anteater dug into one of the corridors and can now eat all the ants passing through it.
However, just like the ants, the anteater is very picky when it comes to numbers.
It will devour a passing group if and only if it consists of exactly k ants.
We want to know how many ants the anteater will eat.
给一棵树，对于每个叶子节点，都有g群蚂蚁要从外面进来，每群蚂蚁在行进过程中只要碰到岔路，就将平均地分成岔路口数-1那么多份，然后平均地走向剩下的那些岔路口，余下的蚂蚁自动消失，树上有一个关键边，假如有一群蚂蚁通过了这条边且数量恰好为k，这k只蚂蚁就被吃掉，问一共有多少只蚂蚁被吃掉
输入输出格式
输入格式：
The first line of the standard input contains three integers n, g , k , separated by single spaces.These specify the number of chambers, the number of ant groups and the number of ants the anteater devours at once. The chambers are numbered from 1 to n.
The second line contains g integers ( ), separated by single spaces, where gives the number of ants in the i -th group at every entrance to the ant hill. The n-1 lines that follow describe the corridors within the ant hill;the i -th such line contains two integers ( ), separated by a single space, that indicate that the chambers no. and are linked by a corridor. The anteater has dug into the corridor that appears first on input.
输出格式：
Your program should print to the standard output a single line containing a single integer: the number of ants eaten by the anteater.
我们如果把那条需要计算贡献的边断开
就变成了两个子树，非常的友好， 我们发现询问和询问之间是独立的，所以我们可以考虑把每个点所有讯问的贡献一起统计
这样我们只需要DP出每个点合法的最大权值和最小权值，然后二分查找一下就好了
挂在二分边界上，wuwuwuwu
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define LL long long
inline LL read(){
LL res=0,w=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
return w*res;
}
struct Edge{LL next,v;}E[N<<1];
LL S,T,cnt=0,k,n,m,head[N],d[N];
LL maxv[N],minv[N],num[N],ans,maxq=0;
vector<int> g;
void add(LL u,LL v){
E[++cnt]=(Edge){head[u],v};head[u]=cnt;
E[++cnt]=(Edge){head[v],u};head[v]=cnt;
d[u]++;d[v]++;
}
void dfs(LL u,LL fa){
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa)continue;
maxv[v]=(maxv[u]+1)*(d[u]-1)-1;
maxv[v]=min(maxq,maxv[v]);
minv[v]=minv[u]*(d[u]-1);
if(minv[v]<=maxq)dfs(v,u);
}
}
LL check(LL vl){
int l=1,r=m,ans=m+1;//注意二分边界
while(l<=r){
int mid=(l+r)>>1;
if(num[mid]>vl)ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main(){
n=read();m=read();k=read();
for(int i=1;i<=m;i++)num[i]=read(),maxq=max(maxq,num[i]);
sort(num+1,num+m+1);
for(int i=1;i<n;i++){
int u=read(),v=read();
if(i==1)S=u,T=v;
add(u,v);
}
for(int i=1;i<=n;i++)if(d[i]==1)g.push_back(i);
maxv[S]=minv[S]=k;
maxv[T]=minv[T]=k;
dfs(S,T);
dfs(T,S);
for(int i=0;i<g.size();i++)
ans+=check(maxv[g[i]])-check(minv[g[i]]-1);
printf("%lld\n",1ll*ans*k);
}