题解 P5351 【Ruri Loves Maschera】

mrsrz · 2019-05-06 15:24:14 · 题解

点分治+树状数组即可。

树上的路径统计问题，很容易想到点分治。

每次分治的时候，我们对当前连通块，求出所有从根出发的路径的价值。

然后考虑如何合并这些链。

我们把所有的链按照其魔力值排序，然后从小到大枚举。对每条链，设其魔力值为w，它与其之前枚举到的链产生的贡献均为w。用树状数组来支持单点修改、区间查询，然后对每条链，在树状数组上查询之前有多少满足边数限制的链即可。然后再把这条链放进树状数组里。

注意减去同一棵子树内的贡献。

答案最后乘2即可。

时间复杂度O(n\log^2 n)。

Code：

#include<cstdio>
#include<vector>
#include<algorithm>
const int N=1e5+7;
typedef long long LL;
LL ans;
int n,L,R;
struct edge{
    int to,nxt,w;
}e[N<<1];
int head[N],cnt,mx[N],sz[N],all,rt,vis[N];
void getrt(int now,int pre){
    mx[now]=0,sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].to]&&e[i].to!=pre)getrt(e[i].to,now),sz[now]+=sz[e[i].to],mx[now]=std::max(mx[now],sz[e[i].to]);
    mx[now]=std::max(mx[now],all-sz[now]);
    if(!rt||mx[now]<mx[rt])rt=now;
}
int B[N];
inline void add(int i,int x){for(;i<=R;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i^=i&-i)x+=B[i];return x;}
std::vector<std::pair<int,int>>al,tt;
void dfs(int now,int pre,int len,int val){
    tt.emplace_back(val,len);
    if(len<R)
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=pre&&!vis[e[i].to])dfs(e[i].to,now,len+1,std::max(val,e[i].w));
}
void doit(int now){
    al.clear();
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        tt.clear();
        dfs(e[i].to,now,1,e[i].w);
        std::sort(tt.begin(),tt.end());
        for(int t=0;t<tt.size();++t)
        ans-=(LL)tt[t].first*(ask(R-tt[t].second)-ask(std::max(0,L-tt[t].second-1))),add(tt[t].second,1);
        for(int t=0;t<tt.size();++t)add(tt[t].second,-1);
        for(auto t:tt)al.push_back(t);
    }
    std::sort(al.begin(),al.end());
    for(int t=0;t<al.size();++t)
    ans+=(LL)al[t].first*(ask(R-al[t].second)-ask(std::max(0,L-al[t].second-1))),add(al[t].second,1);
    for(int t=0;t<al.size();++t)add(al[t].second,-1);
    for(auto t:al)
    if(t.second>=L)ans+=t.first;
}
void solve(int now){
    vis[now]=1,doit(now);
    const int sm=all;
    for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
        rt=0;
        all=sz[e[i].to]<sz[now]?sz[e[i].to]:sm-sz[now];
        getrt(e[i].to,now),solve(rt);
    }
}
int main(){
    scanf("%d%d%d",&n,&L,&R);
    for(int i=1;i<n;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    rt=0,all=n;
    getrt(1,0),solve(rt);
    printf("%lld\n",ans<<1);
    return 0;
}