bzoj_1468 Tree

题目:

  给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K。

思路:

  • 关于点分治:
      如果在树上统计路径,可以枚举树上一点,计算出所有经过这一点的路径,再删去这个点,在其他子树内递归处理。这样的暴力复杂度是 。但是如果每次选中的点为重心,根据重心的性质,剩下的每个子树大小都是当前大小的一半,所以复杂度就能达到 了。
  • 关于此题:
      设 为当前的重心,处理出 代表 间的距离。那么只要排序后扫描一遍(类似尺取)就能得到 的点对个数了。但是这样得到的点对并不是全部符合要求。设 的一个儿子,如果满足 (此时 为到 的距离),那么这个点对是不经过 的。考虑完了所有经过 的点对,就可以去掉 ,递归解决问题了。
      根据点分治的复杂度计算,每个点就最多被遍历到次。加上排序的复杂度,总共是

代码:

#include <bits/stdc++.h>
#define MN 40005
#define ll long long
#define clr(a,b) memset(a,b,sizeof a)
using namespace std;
template<class T>bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T>bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<int N,int M,class T>struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(x,G,v) for(int x=G.HEAD[v];x;x=G.NXT[x])
};
struct Edge{
    int to,w;
};
Link<MN,MN<<1,Edge> G;
int siz[MN],maxv[MN],vis[MN];
void dfs_siz(int o,int f,int all,int &rt,int &Min){
    siz[o]=1;maxv[o]=0;
    EOR(k,G,o){
        Edge e=G[k];
        if(e.to==f||vis[e.to])continue;
        dfs_siz(e.to,o,all,rt,Min);
        tomax(maxv[o],siz[e.to]);
        siz[o]+=siz[e.to];
    }
    if(tomin(Min,max(all-siz[o],maxv[o])))
        rt=o;
}
#define inf 2100000000
int getRt(int x,int all){
    int ans=x,Min=inf;
    dfs_siz(x,0,all,ans,Min);
    return ans;
}
int dis[MN],tot;
void dfs_dis(int o,int f,int w){
    dis[++tot]=w;
    EOR(k,G,o){
        Edge e=G[k];
        if(e.to==f||vis[e.to])continue;
        dfs_dis(e.to,o,w+e.w);
    }
}
int k;
ll calc(int x,int w){
    ll ans=0;
    tot=0;dfs_dis(x,0,w);
    sort(dis+1,dis+1+tot);
    int l=1,r=tot;
    while(l<r){
        while(l<r&&dis[l]+dis[r]>k)r--;
        ans+=r-l;
        l++;
    }
    return ans;
}
ll solve(int o,int all){
    o=getRt(o,all);
    ll ans=calc(o,0);
    vis[o]=1;
    EOR(k,G,o){
        Edge e=G[k];
        if(vis[e.to])continue;
        ans-=calc(e.to,e.w);
        ans+=solve(e.to,siz[e.to]);
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1,a,b,c;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        G.add(a,(Edge){b,c});
        G.add(b,(Edge){a,c});
    }
    scanf("%d",&k);
    cout<<solve(1,n)<<endl;
    return 0;
}