文章目录
介绍：题目：做法：模板题 [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806)代码：
介绍：
将原问题分解成若干相同形式，相互独立的子问题，各个击破 一般用来解决有关树上路径的统计和询问
题目：
P4178 Tree 给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。
做法：
暴力做法；(O(n2)) 点分治做法： 选择一个点作为分治中心，令其为rt做dfs。对于一条路径path(u,v)，其要么经过rt(即lca(u,v) = = rt)，要么在某个子树sub(son[rt])中 把问题形式化为：
solve(T
,rt
) = 统计T树中经过rt且长度
<=k的路径数量
对T数进行分治work(T)的步骤： 1.找到一个分治中心rt 2.ans+=solve(T,rt)//统计答案(统计所有穿过化的路径) 3.对所有rt的子节点v，递归调用work(v)
int work(u
)
{
rt
=find_rt();
ans
=solve(rt
);
for v∈son
[u
]:
ans
+=work(v
)
return ans
;
}
所有合法路径在上述分治过程中被不重不漏地统计到 详细过程：
假设高度一共有h层，经过h层递归后到达边界，每一层子问题互不重叠， 每一层都是O(N) 总复杂度：O(H*N)
我们控制H的大小 （H = 递归的层数） 点分治的复杂度被以下两个条件保证： 1.h=O(log n)，每次选T的重心作为rt(重心满足删除后形成的子树大小为之前一半) 2.找重心以及统计答案solve(T,rt)的复杂度=O(size(T)),或者带log，不与n相关 条件1保证每递归一层size(T)减半，log层到达边界 条件2保证每层复杂度为O(n)或者O(nlog n) 点分治总复杂度 O(log n )或O(nlog2n)，取决于solve是否带log。
模板题 P3806 【模板】点分治1
题目描述 给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std
;
int read()
{
int f
=1,x
=0;
char ss
=getchar();
while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}
while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}
return f
*x
;
}
const int inf
=10000000;
const int maxn
=100010;
int n
,m
;
struct node
{int v
,dis
,nxt
;}E
[maxn
<<1];
int tot
,head
[maxn
];
int maxp
[maxn
],size
[maxn
],dis
[maxn
],rem
[maxn
];
int vis
[maxn
],test
[inf
],judge
[inf
],q
[maxn
];
int query
[1010];
int sum
,rt
;
int ans
;
void add(int u
,int v
,int dis
)
{
E
[++tot
].nxt
=head
[u
];
E
[tot
].v
=v
;
E
[tot
].dis
=dis
;
head
[u
]=tot
;
}
void getrt(int u
,int pa
)
{
size
[u
]=1; maxp
[u
]=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==pa
||vis
[v
]) continue;
getrt(v
,u
);
size
[u
]+=size
[v
];
maxp
[u
]=max(maxp
[u
],size
[v
]);
}
maxp
[u
]=max(maxp
[u
],sum
-size
[u
]);
if(maxp
[u
]<maxp
[rt
]) rt
=u
;
}
void getdis(int u
,int fa
)
{
rem
[++rem
[0]]=dis
[u
];
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(v
==fa
||vis
[v
])continue;
dis
[v
]=dis
[u
]+E
[i
].dis
;
getdis(v
,u
);
}
}
void calc(int u
)
{
int p
=0;
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
rem
[0]=0; dis
[v
]=E
[i
].dis
;
getdis(v
,u
);
for(int j
=rem
[0];j
;--j
)
for(int k
=1;k
<=m
;++k
)
{
if(query
[k
]>=rem
[j
])
test
[k
]|=judge
[query
[k
]-rem
[j
]];
}
for(int j
=rem
[0];j
;--j
)
{
q
[++p
]=rem
[j
];
judge
[rem
[j
]]=1;
}
}
for(int i
=1;i
<=p
;++i
)
judge
[q
[i
]]=0;
}
void solve(int u
)
{
vis
[u
]=judge
[0]=1; calc(u
);
for(int i
=head
[u
];i
;i
=E
[i
].nxt
)
{
int v
=E
[i
].v
;
if(vis
[v
])continue;
sum
=size
[v
]; maxp
[rt
=0]=inf
;
getrt(v
,0); solve(rt
);
}
}
int main()
{
n
=read();m
=read();
for(int i
=1;i
<n
;++i
)
{
int u
=read(),v
=read(),dis
=read();
add(u
,v
,dis
);add(v
,u
,dis
);
}
for(int i
=1;i
<=m
;++i
)
query
[i
]=read();
maxp
[rt
]=sum
=n
;
getrt(1,0);
solve(rt
);
for(int i
=1;i
<=m
;++i
)
{
if(test
[i
]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
