做网站以后的趋势/厦门人才网最新招聘信息网

poj1741

题意:给你一颗有边权的树，询问满足i点到j点距离不大于k的二元组个数。

点分治的入门题目。

前置技能:

树的重心:即以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。在对树进行分治的时候可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度。

会求以当前树为根节点的子树中节点个数，会求以当前节点为根的子树中所有节点到当前节点的距离。

下面开始开始介绍关于树的点分治问题。

我们可以先求出当前节点为根的所有节点到当前节点的距离存入dis数组，然后从小到大排个序。我们要求的答案就是经过当前根节点的且(dis[i]+dis[j])<=k的二元组有多少个，用尺取法我们可以得到当前子树中有多少二元组满足(dis[i]+dis[j])<=k，但这样求的答案会算上有些没有经过根节点的那些答案。我们需要在减去那些没经过root的答案。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
const int MAXN=50005;
int n,m,k;
struct node{int to,next,l;
}e[MAXN*2];
int head[MAXN],tot;
void addedge(int u,int v,int l)
{e[tot].l=l;e[tot].to=v;e[tot].next=head[u];head[u]=tot++;
}
int root,num,ans,min_root;
int vis[MAXN],son[MAXN],max_son[MAXN];
int dis[MAXN];
void init()
{tot=0;ans=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));
}
void dfs_size(int u,int fa)//每个节点为根的子树的节点数量
{son[u]=1;max_son[u]=0;for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(vis[v]||v==fa) continue;dfs_size(v,u);son[u]+=son[v];if(max_son[u]<son[v]) max_son[u]=son[v];}
}
void dfs_root(int r,int u,int fa)		//寻找重心 
{max_son[u]=max(max_son[u],son[r]-son[u]);if(max_son[u]<min_root){min_root=max_son[u];root=u;}for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa||vis[v]) continue;dfs_root(r,v,u);}return ;
}
void dfs_dis(int u,int d,int fa)		//每个节点到根节点的距离 
{dis[num++]=d;for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(vis[v]||v==fa) continue;dfs_dis(v,d+e[i].l,u);}return ;
}
int cal(int u,int d)
{int res=0;num=0;dfs_dis(u,d,-1);sort(dis,dis+num);int i=0,j=num-1;while(i<j){while(i<j&&dis[i]+dis[j]>k) j--;res+=j-i;i++;}return res;
}
int dfs(int u)
{min_root=n;dfs_size(u,-1); dfs_root(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]){ans-=cal(v,e[i].l);dfs(v);}}
}
int main()
{while(scanf("%d%d",&n,&k)!=EOF){if(n==0||k==0) break;init();for(int i=0;i<n-1;i++){int u,v,l;scanf("%d%d%d",&u,&v,&l);addedge(u,v,l);addedge(v,u,l);}dfs(1);printf("%d\n",ans);}return 0;
}

HDU-5977，依然是点分治，不过把cal函数和dfs_dis函数改了一下，其他的基本一致。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
//普通读入优化
void read(int &x)
{int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;
}typedef long long ll;
const int MAXN=5e5 + 10;
int n,m,k;
struct node{int to,next;
}e[MAXN*2];
int head[MAXN],tot;
void addedge(int u,int v)
{e[tot].to=v;e[tot].next=head[u];head[u]=tot++;
}
int root,num;ll ans;int min_root;
int vis[MAXN],son[MAXN],max_son[MAXN];
int dis[MAXN];
void init()
{tot=0;ans=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));
}
void dfs_size(int u,int fa)//每个节点为根的子树的节点数量
{son[u]=1;max_son[u]=0;for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(vis[v]||v==fa) continue;dfs_size(v,u);son[u]+=son[v];if(max_son[u]<son[v]) max_son[u]=son[v];}
}
void dfs_root(int r,int u,int fa)		//寻找重心 
{max_son[u]=max(max_son[u],son[r]-son[u]);if(max_son[u]<min_root){min_root=max_son[u];root=u;}for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(v==fa||vis[v]) continue;dfs_root(r,v,u);}return ;
}
int a[MAXN],Hash[1200];				//注意Hash数组别开太大，不然会T。 
void dfs_dis(int u,int fa,int s)		//每个节点到根节点的距离 
{dis[num++]=s;for(int i=head[u];~i;i=e[i].next){int v=e[i].to;if(vis[v]||v==fa) continue;dfs_dis(v,u,s|(1<<a[v]));}return ;
}
ll cal(int u,int d)
{ll res=0;num=0;dfs_dis(u,-1,d);memset(Hash,0,sizeof(Hash));for(int i=0;i<num;i++) Hash[dis[i]]++;for(int i=0;i<num;i++){Hash[dis[i]]--;res+=Hash[(1<<k)-1];for(int s0=dis[i];s0;s0=(s0-1)&dis[i])	//枚举子集 {res+=Hash[((1<<k)-1)^s0];}Hash[dis[i]]++;}return res;
}int dfs(int u)
{min_root=n;dfs_size(u,-1); dfs_root(u,u,-1);ans+=cal(root,(1<<a[root]));vis[root]=1; int p=1<<a[root];		//dfs(v)时root会改变，所以要先记录下root。 for(int i=head[root];~i;i=e[i].next){int v=e[i].to;if(!vis[v]){ans-=cal(v,(p|(1<<a[v])));dfs(v);}}
}int main()
{while(scanf("%d%d", &n, &k)==2){if(n==0||k==0) break;init();for(int i=1;i<=n;i++) {read(a[i]);a[i]--;}for(int i=1;i<n;i++){int u,v;read(u);read(v);addedge(u,v);addedge(v,u);}if(k==1){printf("%d\n",n*n);continue;}dfs(1);printf("%lld\n",ans);}return 0;
}