poj 1741Tree(点分治)

题目链接

5 41 2 31 3 11 4 23 5 10 0
Sample Output
8
Source
LouTiancheng@POJ

论文题：论文传送门

题意：

题解

参考博客：传送门

每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心

找到重心后，需要统计所有结点到重心的距离，看其中有多少对小于等于K，这里采用的方法就是把所有的距离存在一个数组里，进行快速排序，这是nlogn的，然后用一个经典的相向搜索O(n)时间内解决。但是这些求出来满足小于等于K的里面只有那些路径经过重心的点对才是有效的，也就是说在同一颗子树上的肯定不算数的，所以对每颗子树，把子树内部的满足条件的点对减去。

最后的复杂度是n logn logn    其中每次快排是nlogn 而递归的深度为logn

注意这里求重心和以往不同，因为每次分治都要对一棵子树求重心，所以这棵树的大小不定，所以要两次dfs。详细操作见代码。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=10000+100;int head[maxn],vis[maxn],dis[maxn];struct edge{    int to,next,w;}e[maxn*2];   //int tol=0;void add(int u,int v,int w){    e[++tol].to=v,e[tol].next=head[u],e[tol].w=w,head[u]=tol;}int root,mi,num;int mx[maxn];int ans=0;int n,k;int tn;int sz[maxn];void dfssize(int u,int f)   //处理子树大小{    sz[u]=1;mx[u]=0;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==f||vis[v]) continue;        dfssize(v,u);        sz[u]+=sz[v];        if(sz[v]>mx[u]) mx[u]=sz[u];    }}void dfsroot(int r,int u,int f)    //求重心{    if(sz[r]-sz[u]>mx[u]) mx[u]=sz[r]-sz[u];    if(mi>mx[u])    {        mi=mx[u];        root=u;    }    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==f) continue;        dfsroot(r,v,u);    }}void getdis(int u,int f,int d)//求距离{    dis[num++]=d;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==f) continue;        getdis(v,u,d+e[i].w);    }}int cal(int u,int d){    int res=0;    num=0;    getdis(u,-1,d);    sort(dis,dis+num);    int i=0,j=num-1;    while(i<j)  //求u为根子树中有多少对满足条件    {        while(i<j&&dis[i]+dis[j]>k) j--;        res+=j-i;        i++;    }    return res;}void dfs(int u){    mi=inf;    dfssize(u,-1);       //这一步和下面的一步求出重心    dfsroot(u,u,-1);    ans+=cal(root,0);    vis[root]=1;         //将这个根处理完后打上标记“去掉”    for(int i=head[root];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]) continue;        ans-=cal(v,e[i].w);        dfs(v);    }}int main(){    while(~scanf("%d%d",&n,&k))    {        if(n==0&&k==0) break;        tol=0;ans=0;        memset(head,0,sizeof(head));        memset(sz,0,sizeof(sz));        memset(vis,0,sizeof(vis));        memset(dis,0,sizeof(dis));        rep(i,1,n)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            add(u,v,w),add(v,u,w);        }        dfs(1);        printf("%d/n",ans);    }    return 0;}