点分治
目录
点分治是一种基于树的重心，统计树上路径的优秀算法。将树上的路径分为经过树的重心和不经过树的重心两种，同时利用树的重心性质，使得递归深度不超过 (logn)次。总的时间复杂度为(nlog^2n) 。
【题意】：poj_1741 求解一个树上所有边的和不超过k的共有多少个
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
int n,k,tot,root,cnt,ans,scale;
int head[maxn],size[maxn],maxson[maxn],dis[maxn];
//size[i]为以i为根的子树的大小，dis[i]为i到根的距离
bool vis[maxn];
struct Edge
{
int nex,to,val;
}edge[maxn<<1];
void add(int from,int to,int val)
{
edge[++tot].nex=head[from];
edge[tot].val=val;
edge[tot].to=to;
head[from]=tot;
}
void getroot(int u,int fa)
{
size[u]=1;
maxson[u]=0;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa||vis[v]) continue;
getroot(v,u);
size[u]+=size[v];
maxson[u]=max(maxson[u],size[v]);
}
maxson[u]=max(maxson[u],scale-maxson[u]);
if(maxson[u]<maxson[root]) root=u;
}
void getdis(int u,int fa,int val) //val是u到目标点的距离，fa是u的父亲
{ //求出所有点到该子树根节点的距离
dis[++cnt]=val;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa||vis[v]) continue;
getdis(v,u,val+edge[i].val);
}
}
int calc(int u,int val)
{
cnt=0;
getdis(u,0,val);
int l=1,r=cnt,sum=0;
sort(dis+1,dis+cnt+1);
while(1) //不考虑非法双指正扫描求出满足的边的个数(非法会在后面减去)
{
while(r&&dis[l]+dis[r]>k) r--;
if(r<l) break;
sum+=r-l;
l++;
}
return sum;
}
void solve(int u)
{
ans+=calc(u,0);
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(vis[v]) continue;
ans-=calc(v,edge[i].val); //容斥定理
root=0; //开始分治每一颗子树
scale=size[v]; //子树的规模
getroot(v,0);
solve(root);
}
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
if(!(n||k)) break;
tot=ans=0;
memset(vis,false,sizeof(vis));
memset(head,-1,sizeof(head));
for(int i=1;i<n;++i){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
maxson[0]=inf;
scale=n;
getroot(1,0);
solve(root);
printf("%d
",ans);
}
}
[题意]：洛谷P 3806；m个询问，每个询问输入一个k，求能不能满足有边的权值正好等于k。
点分治所有可能的k都提前打表到数组即可。show code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
int tot,n,m,k,root,cnt,ans[100000010],scale;
int head[maxn],dis[maxn],maxson[maxn],size[maxn];
bool vis[maxn];
struct Edge
{
int nex,to,val;
}edge[maxn<<1];
void add(int from,int to,int val)
{
edge[++tot].to=to;
edge[tot].val=val;
edge[tot].nex=head[from];
head[from]=tot;
}
void getroot(int u,int fa)
{
size[u]=1;
maxson[u]=0;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa||vis[v]) continue;
getroot(v,u);
size[u]+=size[v];
maxson[u]=max(maxson[u],size[v]);
}
maxson[u]=max(maxson[u],scale-maxson[u]);
if(maxson[u]<maxson[root]) root=u;
}
void getdis(int u,int fa,int val)
{
dis[++cnt]=val;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa||vis[v]) continue;
getdis(v,u,val+edge[i].val);
}
}
void calc(int u,int val,int num) //num为1或-1,因为判断是不是非法
{
cnt=0;
getdis(u,0,val);
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
if(i!=j) ans[dis[i]+dis[j]]+=num;
}
void solve(int u)
{
calc(u,0,1);
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
int v=edge[i].to;
if(vis[v]) continue;
calc(v,edge[i].val,-1);
root=0;
scale=size[v];
getroot(v,0);
solve(root);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
head[i]=-1,vis[i]=false;
}
tot=0;
for(int i=1;i<n;++i){
int a,b,val;
scanf("%d %d %d",&a,&b,&val);
add(a,b,val);
add(b,a,val);
}
maxson[0]=inf;
scale=n;
getroot(1,0);
solve(root);
while(m--)
{
scanf("%d",&k);
ans[k]?printf("AYE
"):printf("NAY
");
}
system("pause");
}