Life Lies in Movement 题解

· · 题解

变一下这个式子：

\frac{\sum_{x=1}^nf(x,u,v)}{n}\ge \frac{1}{2}\operatorname{dis}(u,v)+k 2\sum_{x=1}^nf(x,u,v)\ge n\times \operatorname{dis}(u,v)+2nk 2\sum_{x=1}^nf(x,u,v)-n\times \operatorname{dis}(u,v)\ge 2nk

注意到 f(x,u,v)+f(x,v,u)=\operatorname{dis}(u,v)。

所以 \sum_{x=1}^n(f(x,u,v)+f(x,v,u))=n\times \operatorname{dis}(u,v)。

于是：

2\sum_{x=1}^nf(x,u,v)-\sum_{x=1}^n(f(x,v,u)+f(x,u,v))\ge 2nk \sum_{x=1}^n(f(x,u,v)-f(x,v,u))\ge 2nk

设 K=2nk。

注意到 f(x,u,v)-f(x,v,u)=\operatorname{dis}(x,v)-\operatorname{dis}(x,u)。

所以：

\sum_{x=1}^n(\operatorname{dis}(x,v)-\operatorname{dis}(x,u))\ge K

设 s_u=\sum_{x=1}^n \operatorname{dis}(x,u)。

则：

s_v-s_u\ge K

简单换根算出所有点的 s 之后排序，双指针即可。

时间复杂度 O(n\log n)，瓶颈在于排序。

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
ll read()
{
    ll num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+(ch-'0');
        ch=getchar();
    }
    return num;
}
void print(cll x)
{
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    print(x/10);
    putchar(x%10+'0');
}
void princh(cll x,const char ch)
{
    print(x);
    putchar(ch);
}
int n;
ll k,K;
int head[1000001];
struct edge{
    int to,nxt,val;
}e[2000000];
int tot;
void add_edge(cint u,cint v,cint val)
{
    e[++tot]=edge{u,head[v],val};
    head[v]=tot;
    e[++tot]=edge{v,head[u],val};
    head[u]=tot;
}
int siz[1000001];
ll a[1000001];
void dfs(cint u,cint father,cll dep)
{
    siz[u]=1;
    a[1]+=dep;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(e[i].to==father)continue;
        dfs(e[i].to,u,dep+e[i].val);
        siz[u]+=siz[e[i].to];
    }
}
void calc(cint u,cint father)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(e[i].to==father)continue;
        a[e[i].to]=a[u]-1ll*siz[e[i].to]*e[i].val+1ll*(n-siz[e[i].to])*e[i].val;
        calc(e[i].to,u);
    }
}
int l;
ll ans;
void solve()
{
    n=read();
    k=read();
    K=n*k<<1;
    tot=ans=0;
    for(int i=1;i<=n;++i)head[i]=0;
    for(int i=1;i<n;++i)
    {
        cint u=read(),v=read(),val=read();
        add_edge(u,v,val);
    }
    dfs(1,0,0);
    calc(1,0);
    sort(a+1,a+n+1);
    l=0;
    for(int i=1;i<=n;++i)
    {
        while(a[l+1]<=a[i]-K)++l;
        ans+=l;
    }
    princh(ans,'\n');
}
int main()
{
    int T=read();
    while(T--)solve();
    return 0;
}