点分治
以树的重心为根，对子树内的问题分治求解，时间复杂度可以做到 \(O(n\log n\times F(n))\)，其中 \(F(n)\) 是解决经过根的问题所需要的处理。
P3806 模版
给一棵有边权的树，多次询问树上是否存在距离为 \(k\) 的点对。
\(n\le 10^4,m\le 100,k\le 10^7\)
假设现在 \(rt\) 是根，则问题转化为求是否存在不在 \(rt\) 同一子树内的 \(u,v\) 使得 \(dis(rt,u)+dis(rt,v)=k\)。
转化一下式子得 \(dis(rt,u)=k-dis(rt,v)\)，我们记 \(is[x]\) 表示是否出现过 \(x\)，即对于每一个 \(u\)，如果 \(is[k-dis(rt,v)]=1\)，则说明有解；对于不在同一子树的限制，直接对于每个子树处理完再加入 \(is\) 就能避免。
时间复杂度 \(O(mn\log n)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+3;
const int inf=0x3f3f3f3f;
int n,m;
struct edge{
int v,w;
edge(int v=0,int w=0): v(v),w(w){}
};
vector<edge>e[maxn];
int rt;
int siz[maxn],mxsiz[maxn];
int dis[maxn];
int quest[maxn];
vector<int>d;
queue<int>q;
bool isk[10000003];
bool vis[maxn];
bool ans[maxn];
int maxk,sum;
void add(int u,int v,int w){
e[u].emplace_back(edge(v,w));
e[v].emplace_back(edge(u,w));
}
void centroid(int u,int fa){
siz[u]=1; mxsiz[u]=0;
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
centroid(v.v,u);
siz[u]+=siz[v.v];
mxsiz[u]=max(mxsiz[u],siz[v.v]);
}
}
mxsiz[u]=max(mxsiz[u],sum-siz[u]);
if(!rt||mxsiz[u]<mxsiz[rt]){
rt=u;
}
}
void distance(int u,int fa){
d.emplace_back(dis[u]);
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
dis[v.v]=dis[u]+v.w;
distance(v.v,u);
}
}
}
void dfz(int u,int fa){
isk[0]=1;
q.push(0);
vis[u]=1;
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
dis[v.v]=v.w;
distance(v.v,u);
for(int i:d){
for(int j=1;j<=m;j++){
if(quest[j]>=i){
ans[j]|=isk[quest[j]-i];
}
}
}
while(!d.empty()){
int i=d.back();
if(i<=maxk){
q.push(i);
isk[i]=1;
}
d.pop_back();
}
}
}
while(!q.empty()){
isk[q.front()]=0;
q.pop();
}
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
sum=siz[v.v];
rt=0;
mxsiz[rt]=inf;
centroid(v.v,u);
centroid(rt,0);
dfz(rt,0);
}
}
}
signed main(){
cin>>n>>m;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
add(u,v,w);
}
for(int i=1;i<=m;i++){
cin>>quest[i];
maxk=max(maxk,quest[i]);
}
sum=n;
rt=0;
mxsiz[rt]=inf;
centroid(1,0);
centroid(rt,0);
dfz(rt,0);
for(int i=1;i<=m;i++){
if(ans[i]){
cout<<"AYE\n";
}else{
cout<<"NAY\n";
}
}
return 0;
}
P4178 Tree
给一棵有边权的树，求树上距离 \(\le k\) 的点对数。
\(n\le 4\times 10^4,k\le 2\times 10^4\)
做法一：
思路同板子，同理转化一下式子得 \(dis(rt,u)\le k-dis(rt,v)\) 这个偏序问题非常经典，直接树状数组维护即可。
时间复杂度 \(O(n\log n\log k)\)。
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+3;
const int inf=0x3f3f3f3f;
int n,m;
struct edge{
int v,w;
edge(int v=0,int w=0): v(v),w(w){}
};
vector<edge>e[maxn];
int rt;
int siz[maxn],mxsiz[maxn];
int dis[maxn];
int quest[maxn];
vector<int>d;
queue<int>q;
int tree[maxn];
bool vis[maxn];
int ans[maxn];
int maxk,sum;
void add(int u,int v,int w){
e[u].emplace_back(edge(v,w));
e[v].emplace_back(edge(u,w));
}
int lowbit(int x){return x&-x;}
void modify(int x,int c){
x++;
for(;x<=maxk+1;x+=lowbit(x)) tree[x]+=c;
}
int query(int x){
x++;
int ret=0;
for(;x;x-=lowbit(x)) ret+=tree[x];
return ret;
}
void centroid(int u,int fa){
siz[u]=1; mxsiz[u]=0;
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
centroid(v.v,u);
siz[u]+=siz[v.v];
mxsiz[u]=max(mxsiz[u],siz[v.v]);
}
}
mxsiz[u]=max(mxsiz[u],sum-siz[u]);
if(!rt||mxsiz[u]<mxsiz[rt]){
rt=u;
}
}
void distance(int u,int fa){
d.emplace_back(dis[u]);
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
dis[v.v]=dis[u]+v.w;
distance(v.v,u);
}
}
}
void dfz(int u,int fa){
modify(0,1);
q.push(0);
vis[u]=1;
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
dis[v.v]=v.w;
distance(v.v,u);
for(int i:d){
for(int j=1;j<=m;j++){
if(quest[j]>=i){
ans[j]+=query(quest[j]-i);
}
}
}
while(!d.empty()){
int i=d.back();
if(i<=maxk){
q.push(i);
modify(i,1);
}
d.pop_back();
}
}
}
while(!q.empty()){
modify(q.front(),-1);
q.pop();
}
for(edge v:e[u]){
if(v.v!=fa&&!vis[v.v]){
sum=siz[v.v];
rt=0;
mxsiz[rt]=inf;
centroid(v.v,u);
centroid(rt,0);
dfz(rt,0);
}
}
}
signed main(){
cin>>n;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
add(u,v,w);
}
m=1;
for(int i=1;i<=m;i++){
cin>>quest[i];
maxk=max(maxk,quest[i]);
}
sum=n;
rt=0;
mxsiz[rt]=inf;
centroid(1,0);
centroid(rt,0);
dfz(rt,0);
for(int i=1;i<=m;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
做法二：
CF293E Close Vertices
给一棵有边权的树，求树上距离 \(\le k\)，边数 \(\le l\) 的点对数。
\(l\le n\le 10^5,k\le 10^9\)
时间复杂度 \(O(n\log^2 n)\)。
标签：rt,le,int,分治,maxn,mxsiz,dis From： https://www.cnblogs.com/DEV3937/p/18359030/dfz