P3576 [POI 2014] MRO-Ant colony

洛谷

一个比较简单的思路，不需要二分。

考虑逆向操作，从路径两端开始处理数值范围，将蚂蚁群大小视为一次查询。

由于树的两点之间的简单路径只有一条，所以每个点的范围是唯一的。

处理时和 \(10^9\) 取最小值，因为此时已经超过了蚁群最大数量，再继续可能会把 long long 爆了。

之后我们再把叶子节点的范围找出来，做一个类似差分的操作即可，具体可以看代码。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,g,k,m[1000005],d[1000005],l[1000005],r[1000005],cnt,cnt2,ans;
vector<int> e[1000005];
struct P{int op,v;
}a[3000005];
bool cmp(P a,P b){if(a.v!=b.v)return a.v<b.v;return a.op<b.op;
}
void dfs(int p,int f){for(int i:e[p]){if(i==f)continue;if(d[i]==1){l[i]=l[p],r[i]=r[p];}else {l[i]=l[p]*(d[i]-1);r[i]=r[p]*(d[i]-1)+d[i]-2;}dfs(i,p);}
}
signed main(){cin>>n>>g>>k;for(int i=1;i<=g;i++)scanf("%d",&m[i]);int x,y;cin>>x>>y;e[x].push_back(y);e[y].push_back(x);d[y]++,d[x]++;for(int i=2,u,v;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);d[u]++,d[v]++;}if(d[x]==1)l[x]=r[x]=k;else l[x]=r[x]=k*(d[x]-1);if(d[y]==1)l[y]=r[y]=k;else l[y]=r[y]=k*(d[y]-1);dfs(x,y);dfs(y,x);for(int i=1;i<=n;i++)if(d[i]==1)a[++cnt2]={1,l[i]},a[++cnt2]={3,r[i]};for(int i=1;i<=n;i++)a[++cnt2]={2,m[i]};sort(a+1,a+cnt2+1,cmp);for(int i=1,s=0;i<=cnt2;i++){if(a[i].op==2)ans+=s;else if(a[i].op==1)s++;else s--;}cout<<ans*k;return 0;
}