Lvat_s Blog

一模一样的点分治……

为了凑博客数又复制了一遍

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
  
int n,k,h[40005],en,mx[40005],siz[40005],ans,root,val,vis[40005],temp[40005],cnt;
  
struct Edge{
int b,v,next;
}e[80005];
  
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
  
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
  
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
  
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
  
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
//for(int i=1;i<=cnt;i++)printf("Temp:%d\n",temp[i]);
int i=1,j=cnt;
while(i<j){
    while(temp[i]+temp[j]>k && i<j)j--;
    now+=j-i;
    i++;
}
//printf("Now:%d\n",now);
return now;
}
  
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
//printf("Ans:%d\n",ans);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        ans-=Cal(v,e[i].v);
        Dfs(v);
    }
}
}
  
int main(){
freopen("1468.in","r",stdin);
freopen("1468.out","w",stdout);
scanf("%d",&n);
//memset(h,0,sizeof(h));
//memset(vis,0,sizeof(vis));
//ans=en=0;
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    AddEdge(sa,sb,sc);
    AddEdge(sb,sa,sc);
}
scanf("%d",&k);
Dfs(1);
printf("%d\n",ans);
return 0;
}