POJ 2114 （点分治）

题目：https://vjudge.net/contest/307753#problem/B

题意：求树中路径和=k的点对是否存在

思路：点分治，这个题其实和上一题洛谷一样，只是这个数据强，我们不能直接预处理所有可能的路径长度，预处理所有路径长度复杂度 O（n^2） ,我们改为直接每次查询都分治一遍，我们只要把solve在O(n)求出来，那时间复杂度就是 O(n*logn*logn),时间上快了很多，其实等于k这个可以使用我们之前的方法。直接把不大于k的路径-小于k的路径=等于k的路径，然后搞一搞就可以了

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<iostream>

#include<vector>

#define maxn 100005

#define mod 1e19

using namespace std;

typedef long long ll;

ll da;

vector<pair<ll,ll> > mp[maxn];//存下图

bool vis[maxn];//标记曾经使用过的重心

ll maxsize[maxn],dis[maxn],d[maxn];//maxsize 当前节点的最大子树

ll siz[maxn],e[maxn];// dis 到重心的距离  d 出现过的距离

ll n,m,rt,sum,qe;  // siz 当前节点的子树个数  e 出现的距离  rt代表当前重心

void find(ll x,ll f){//找出重心

    siz[x]=;

    maxsize[x]=;

    for(int i=;i<mp[x].size();i++){

        pair<ll,ll> q=mp[x][i];

        if(q.first==f||vis[q.first]) continue;//vis数组标记曾经使用过的重心

        find(q.first,x);

        siz[x]+=siz[q.first];

        maxsize[x]=max(maxsize[x],siz[q.first]);

    }

    maxsize[x]=max(maxsize[x],sum-siz[x]);//节点总数减去当前的子树数=以当前节点为根的父亲点子树数

    if(maxsize[x]<maxsize[rt]){

        rt=x;

    }

}

void get_dis(ll x,ll f,ll len){

    e[++qe]=len;

    for(int i=;i<mp[x].size();i++){

        pair<ll,ll> q=mp[x][i];

        if(q.first==f||vis[q.first]) continue;

        dis[q.first]=dis[x]+len;

        get_dis(q.first,x,len+q.second);

    }

}

ll solve(ll x,ll len){

    ll ee=;

    qe=;

    dis[x]=len;

    get_dis(x,,len);

    sort(e+,e+qe+);

    ll l=,r=qe;

    while(l<r){

        if(e[l]+e[r]<=m){

            ee+=r-l;

            l++;

        }

        else{

            r--;

        }

    }

    return ee;

}

void divide(ll x){

    da+=solve(x,);

    vis[x]=;

    for(int i=;i<mp[x].size();i++){

        pair<ll,ll> q=mp[x][i];

        if(vis[q.first]) continue;

        da-=solve(q.first,q.second);

        sum=siz[q.first];

        rt=;

        maxsize[rt]=mod;

        find(q.first,x);

        divide(rt);

    }

}

void init(){

    da=;

    for(int i=;i<=n;i++) mp[i].clear();

    for(int i=;i<=n;i++) vis[i]=;

}

int main(){

    while(scanf("%lld%lld",&n,&m)!=EOF)

    {

        if(n==&&m==) break;

        ll a,b,c;

        init();

        char s[];

        for(int i=;i<n-;i++){

            scanf("%lld%lld%lld%s",&a,&b,&c,s);

            //a++;

            //b++;

            mp[a].push_back(make_pair(b,c));

            mp[b].push_back(make_pair(a,c));

        }

        scanf("%lld",&m);

        sum=n;//当前节点数

        rt=;

        maxsize[]=mod;//置初值

        find(,);

        divide(rt);

        printf("%lld\n",da);

    }

}