BZOJ3872: [Poi2014]Ant colony

因为下取整可以合并，即a/b/c=a/bc，且我们只关心经过某一条边< s,t>的蚂蚁，将树以< s,t>为界砍成两棵树，分别以s，t为根，那么我们只关心这两棵树的叶子到根上方时，有多少个k
对于子树中的叶子i，他走到根上方的分母f[i]已经确定，可以做个简单的dp求，这个叶子的贡献就是g[j]/f[i]（下取整）=k的蚂蚁，即g[j]在[ k∗f[i],(k+1)∗f[i] )的j有多少个，g的顺序无影响，排序后二分求得

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9+1
using namespace std;

inline void read(int &x)
{
    char c; while(!((c=getchar())>='0'&&c<='9'));
    x=c-'0';
    while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
const int maxn = 1100000;

int n,s,t;
struct edge{int y,nex;}a[maxn<<1]; int len,fir[maxn];
inline void ins(const int x,const int y){a[++len]=(edge){y,fir[x]};fir[x]=len;}
int d[maxn],fa[maxn],f[maxn];
bool leaf[maxn];

void dfs(const int x)
{
    for(int k=fir[x],y=a[k].y;k;k=a[k].nex,y=a[k].y) if(y!=fa[x])
    {
        fa[y]=x; 
        if((ll)f[x]*(d[y]-1)>=inf) f[y]=inf;
        else f[y]=f[x]*(d[y]-1);
        dfs(y);
    }
}

int m,g[maxn],k;
int ct(const ll x)
{
    int l=1,r=m;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(g[mid]<=x) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}

int main()
{
    read(n); read(m); read(k);
    for(int i=1;i<=m;i++) read(g[i]);
    sort(g+1,g+m+1);

    read(s); read(t); d[s]=d[t]=1;
    for(int i=2;i<n;i++)
    {
        int x,y; read(x); read(y);
        ins(x,y); ins(y,x); d[x]++,d[y]++;
    }
    for(int i=1;i<=n;i++) if(d[i]==1) d[i]=2,leaf[i]=true;
    f[s]=d[s]-1; dfs(s);
    f[t]=d[t]-1; dfs(t);

    ll re=0;
    for(int i=1;i<=n;i++) if(leaf[i])
    {
        ll L=(ll)k*f[i],R=(ll)(k+1)*f[i]-1ll;
        re+=(ll)k*(ct(R)-ct(L-1ll));
    }
    printf("%lld\n",re);

    return 0;
}