首页 > 代码库 > [poj 1741]Tree 点分治

[poj 1741]Tree 点分治

题意

求树上距离不超过k的点对数,边权<=1000

题解

    点分治。

    点分治的思想就是取一个树的重心,这种路径只有两种情况,就是经过和不经过这个重心,如果不经过重心就把树剖开递归处理,经过就把两边的点瞎那啥统计一下,因为会有完全在子树内的路径,还要容斥算算。

    点分治是O(logn)的,但是每次操作是O(nlogn)那么总时间就是技术分享

#include<map>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<complex>#include<iostream>#include<assert.h>#include<algorithm>using namespace std;#define inf 1001001001#define infll 1001001001001001001LL#define ll long long#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl#define gmax(a,b) (a)=max((a),(b))#define gmin(a,b) (a)=min((a),(b))#define Ri register int#define gc getchar()#define il inlineil int read(){    bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch==-)f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-0;ch=gc;}return f?x:-x;}#define gi read()#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);struct edge{    int to,next,v;} e[23333];int last[20000],cnt;void link(int a,int b,int c){    e[++cnt]=(edge){b,last[a],c};last[a]=cnt;    e[++cnt]=(edge){a,last[b],c};last[b]=cnt;}int siz[23333],f[23333],vis[23333],deep[23333],d[23333],root,sum,ans,n,k;void zy(int x,int fa=-1){    siz[x]=1;f[x]=0;    for(int i=last[x];i;i=e[i].next){        if(e[i].to!=fa&&!vis[e[i].to]){            zy(e[i].to,x);            siz[x]=siz[x]+siz[e[i].to];            f[x]=max(f[x],siz[e[i].to]);        }    }    f[x]=max(f[x],sum-siz[x]);    if(f[x]<f[root])root=x;}void dfs(int x,int fa=-1){    deep[++deep[0]]=d[x];    for(int i=last[x];i;i=e[i].next){        if(e[i].to!=fa&&!vis[e[i].to]){            d[e[i].to]=d[x]+e[i].v;            dfs(e[i].to,x);        }    }}int js(int x,int now){    d[x]=now;deep[0]=0;    dfs(x);    sort(deep+1,deep+deep[0]+1);    int zzyy=0,l,r;    for(int l=1,r=deep[0];l<r;){        if(deep[l]+deep[r]<=k)zzyy=zzyy+r-l,l++;        else --r;        }//f**k;    return zzyy;}void dfz(int x){    ans+=js(x,0);    vis[x]=1;    for(int i=last[x];i;i=e[i].next){        if(!vis[e[i].to]){            ans-=js(e[i].to,e[i].v);            sum=siz[e[i].to];            root=0;            zy(e[i].to,root);            dfz(root);        }    } }int main(){    while(n=gi,k=gi,n&&k){        ans=0,cnt=0,root=0;        memset(vis,0,sizeof(vis));        memset(last,0,sizeof(last));        for(int i=1;i<n;i++){            int a,b,c;            a=gi;b=gi;c=gi;            link(a,b,c);        }        sum=n;f[0]=inf;        zy(1);        dfz(root);        printf("%d\n",ans);    }    return 0;}

[poj 1741]Tree 点分治