@Junlier
2018-08-21T17:16:56.000000Z
字数 2501
阅读 2062
图论——点分治
嗯,蒟蒻我刚学的就记录一下
以洛谷的tree为模板讲解:洛谷题目传送门
了解点分治之前,首先要知道什么是重心(要用到)
简单来说,就是子树最小的那个节点,我们需要O(n)地找到他来保证复杂度
void get_root(rg int now,rg int fm)
{
size[now]=1;rg int num=0;//size[]记录子树大小,num[]为当前的最大子树
for(rg int i=hd[now];i;i=ljl[i].nxt)//遍历
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;//先不管这个vis[]
get_root(qw,now);
size[now]+=size[qw];
num=max(num,size[qw]);
}
num=max(num,tot-size[now]);//tot是总点数
//tot-size[now]是父亲那边(不是儿子)的“子树”大小
if(Max>num)Max=num,root=now;//是否更新
}
个人认为这里还是比较简单的,自己画个图简单明了了
找到重心后把重心删掉,变成两个连通块,再分别找重心,把重心与之前找的重心相连边,不断递归建成一棵新树,就是点分树
&&优点:严格log层(不信自己验证)
这道题暂时不要用,但是是点分治的一个重要知识点……
首先了解几个特点(暂时不用理解,等下自然就懂)
- 边建边算
- 常见问题:
1.是否存在……的路径
2.满足……的路径有几条- 只要点分治之后的处理是线性的,那么总的复杂度一定是nlogn(
只要你不瞎搞)
以tree这道题为例,找到一个重心就处理一定过重心的那条路径的答案,别问我为什么,反正这样是对的,而且时间优秀,不会算重//=_=
嗯,这里有点长了,不想写了,所以安利一波机房大佬的博客理解吧,一时半会真的讲不清,至少我问了很久才懂(主要是不想画图来讲解了,画图就很容易理解了)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 40050
using namespace std;
const int Inf=1e9;
int n,K,cnt,tot,ans;
int Max,root,le,ri;
struct EDGE{
int to,nxt,v;
}ljl[N<<1];
int hd[N];
int size[N],vis[N];
int Q[N],dis[N];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void add(rg int p,rg int q,rg int o)
{
ljl[++cnt]=(EDGE){q,hd[p],o};hd[p]=cnt;
}
void get_root(rg int now,rg int fm)
{
size[now]=1;rg int num=0;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;
get_root(qw,now);
size[now]+=size[qw];
num=max(num,size[qw]);
}
num=max(num,tot-size[now]);
if(Max>num)Max=num,root=now;
}
void get_dis(rg int now,rg int fm)
{
Q[++ri]=dis[now];
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(vis[qw]||qw==fm)continue;
dis[qw]=dis[now]+ljl[i].v;
get_dis(qw,now);
}
}
il int Query(rg int now,rg int base)
{
rg int res=0;
ri=0;dis[now]=base;
le=1;get_dis(now,0);
sort(Q+1,Q+ri+1);
while(le<=ri)
{
if(Q[le]+Q[ri]<=K)res+=ri-le,le++;
else ri--;
}
return res;
}
void divide(rg int now,rg int fm)
{
ans+=Query(now,0);vis[now]=1;
rg int all=tot;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;
ans-=Query(qw,ljl[i].v);
tot=size[now]>size[qw]?size[qw]:all-size[qw];Max=Inf;
get_root(qw,0),divide(qw,0);
}
}
int main()
{
n=read();
for(rg int i=1;i<n;++i)
{
rg int p=read(),q=read(),o=read();
add(p,q,o),add(q,p,o);
}
K=read();
tot=n,Max=Inf;
get_root(1,0);
divide(root,0);
printf("%d\n",ans);
return 0;
}