wy's Blog

1468: Tree

Description

Input

Output

Sample Input

Sample Output

这是一道萌萌哒的点分治。。。

推荐一份材料。。。

漆子超犇的《分治算法在树的路径问题中的应用》

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int N,K,tot,Q,Num;
int first[40010];
int next[80010];
int end[80010];
int value[80010];
int mark[40010];
int size[40010];
int maxx[40010];
int Dist[40010];
int Belong[40010];
int P[40010];
int Focus;
struct Pair{
    int st,nd;
    Pair(int a=0,int b=0){
        st=a; nd=b;
    }
}A[40010];
int cmp(const Pair &x,const Pair &y){
    return x.st<y.st;
}
void Add(int x,int y,int z){
    next[++tot]=first[x]; first[x]=tot; end[tot]=y; value[tot]=z;
    next[++tot]=first[y]; first[y]=tot; end[tot]=x; value[tot]=z;
}
void Search(int x,int fa,int m){
    maxx[x]=m-size[x];
    for (int k=first[x],v;v=end[k],k;k=next[k]){
        if (v==fa) continue;
        if (mark[v]) continue;
        Search(v,x,m);
        maxx[x]=max(maxx[x],size[v]);
    }
    if ((maxx[x]<maxx[Focus])||(!Focus)) Focus=x;
}
void Dfs(int x,int fa){   
    size[x]=1;
    for (int k=first[x],v;v=end[k],k;k=next[k]){
        if (v==fa) continue;
        if (mark[v]) continue;
        Dist[v]=Dist[x]+value[k];
        Belong[v]=Belong[x];
        P[Belong[v]]++;
        A[++Num]=Pair(Dist[v],Belong[v]);
        Dfs(v,x);
        size[x]+=size[v];
    }
}
int QAns(int x){
    mark[x]=1;
    Num=0;
    P[x]=1;
    A[++Num]=Pair(0,x);
    for (int k=first[x],v;v=end[k],k;k=next[k]){
        if (mark[v]) continue;
        P[v]=1;
        Dist[v]=value[k];
        Belong[v]=v;
        A[++Num]=Pair(Dist[v],Belong[v]);
        Dfs(v,x);
    }
    sort(A+1,A+Num+1,cmp);
    int Ans=0;
    int l=1,r=Num;
    for (;l<r;){
        for (;A[l].st+A[r].st>K;){
            P[A[r].nd]--;
            --r;
        }
        if (l>=r) break;
        Ans+=(r-l);
        Ans-=(P[A[l].nd]-1);
        P[A[l].nd]--;
        ++l;
    }
    for (int k=first[x],v;v=end[k],k;k=next[k]){
        if (mark[v]) continue;      
        Focus=0;
        Search(v,x,size[v]);
        Ans+=QAns(Focus);
    }
    return Ans;
}
int main(){
    scanf("%d",&N);
    for (int i=1;i<N;++i){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        Add(x,y,z);
    }    
    scanf("%d",&K);
    Dfs(1,0);
    Search(1,0,size[1]);    
    printf("%d\n",QAns(Focus));     
}