首页 > 代码库 > [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 点分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。