点分治
点分治适合处理大规模的树上路径信息问题。
本质思想是选择一点作为分治中心，将原问题划分为几个相同的子树上的问题，进行递归解决。
常见的用于统计树上有关路径的信息。假设当前选定根节点为 \(rt\)，则符合条件的路径必然是以下两种之一：
- 经过 \(rt\) 或一段在 \(rt\) 上；
- 在 \(rt\) 的子树上。
P3806
给定一棵树，边有权值。
多次询问，查询树上是否有长度为 \(k\) 的路径。
先随意取一个点作为根节点 \(rt\)。对于经过 \(rt\) 的路径，先枚举其所有子节点 \(v\)，以 \(v\) 为根计算 \(v\) 子树中所有节点到 \(rt\) 的距离。
即 \(dis_i\) 为当前节点 \(i\) 到 \(rt\) 的距离，\(pd_{key}\) 为之前处理过的子树中是否存在一个节点 \(v\) 使得 \(dis_v=key\)。
若一个询问的 \(k\) 满足 \(pd_{k-dis_i}=\text{true}\) 则存在一个长度为 \(k\) 的路径。
在计算完 \(v\) 子树中所连的边能否成为答案后，将这些新的距离加入到 \(pd\) 中。
注意清空 \(pd\) 时应将之前占用过的 \(pd\) 位置加入到一个队列中清空，依此来保证时间复杂度。
点分治过程中，每一层的所有递归过程合计对每个点处理一次，假设共递归 \(h\) 层，则总时间复杂度为 \(\mathcal O(hn)\)。
若每次选择子树的重心作为根节点，可以保证递归层数最少，时间复杂度为 \(\mathcal O(n\log n)\)。
const int N=1e4+5;
const int M=1e7+5;
int n,m,q[N],rt,sum,siz[N],dp[N],dis[N],pd[M],ret[N],vis[N],d[N],tot;
vector<tuple<int,int>>G[N];
queue<int>tag;
inline void getroot(int u,int f){
siz[u]=1;dp[u]=0;
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
getroot(v,u);
siz[u]+=siz[v];
dp[u]=max(dp[u],siz[v]);
}
dp[u]=max(dp[u],sum-siz[u]);
if(dp[u]<dp[rt])
rt=u;
}
inline void getdis(int u,int f){
d[++tot]=dis[u];
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
dis[v]=dis[u]+w;
getdis(v,u);
}
}
inline void solve(int u,int f){
pd[0]=vis[u]=1;
tag.push(0);
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
dis[v]=w;
getdis(v,u);
for(int k=1;k<=tot;k++)
for(int i=1;i<=m;i++)
if(q[i]>=d[k])
ret[i]|=pd[q[i]-d[k]];
for(int k=1;k<=tot;k++)
if(d[k]<M)
tag.push(d[k]),pd[d[k]]=1;
tot=0;
}
while(tag.size())
pd[tag.front()]=0,tag.pop();
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
sum=siz[v];
dp[rt=0]=inf;
getroot(v,u);
solve(rt,u);
}
}
signed main(){
sum=n=read();m=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
G[u].eb(mt(v,w));G[v].eb(mt(u,w));
}
for(int i=1;i<=m;i++)
q[i]=read();
dp[rt=0]=inf;
getroot(1,0);
solve(rt,0);
for(int i=1;i<=m;i++)
puts(ret[i]?"AYE":"NAY");
return 0;
}
P4178
给定一棵树，边有权值。
查询树上长度小于等于 \(k\) 的路径数量。
递归时，对于当前根节点 \(rt\)，把每一个子节点到 \(rt\) 的距离排序，然后用类似双指针的方法来求小于等于 \(k\) 的边的数量。
在同一子树内的路径是不合法的，但是同样也会算进答案中。
所以对 \(rt\) 的每一条边进行遍历，利用容斥的思想减去不合法的路径，把经过了从重心到新遍历的点的边两次的路径剪掉，统计答案。
const int N=4e4+5;
int n,k,q[N],rt,sum,siz[N],dp[N],dis[N],ret[N],vis[N],d[N],tot,ans;
vector<tuple<int,int>>G[N];
queue<int>tag;
inline void getroot(int u,int f){
siz[u]=1;dp[u]=0;
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
getroot(v,u);
siz[u]+=siz[v];
dp[u]=max(dp[u],siz[v]);
}
dp[u]=max(dp[u],sum-siz[u]);
if(dp[u]<dp[rt])
rt=u;
}
inline void getdis(int u,int f){
d[++tot]=dis[u];
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
dis[v]=dis[u]+w;
getdis(v,u);
}
}
inline int work(int u,int w){
tot=0;dis[u]=w;
getdis(u,0);
sort(d+1,d+1+tot);
int l=1,r=tot,res=0;
while(l<=r)
if(d[l]+d[r]<=k)
res+=r-l,l++;
else
r--;
return res;
}
inline void solve(int u,int f){
vis[u]=1;ans+=work(u,0);
for(auto[v,w]:G[u])
if(v!=f and !vis[v]){
ans-=work(v,w);
sum=siz[v];
dp[0]=n,rt=0;
getroot(v,u);
solve(rt,u);
}
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
G[u].eb(mt(v,w));G[v].eb(mt(u,w));
}
k=read();
dp[rt=0]=inf;
getroot(1,0);
solve(rt,0);
write(ans);
return c0;
}
P4149
给一棵树，每条边有权。
求一条简单路径，权值和等于 \(k\)，且边的数量最小。
递归时，对于当前根节点 \(rt\)，计算所有经过 \(r\) 的路径，可以开个桶记录。
具体地，令 \(mn_i\) 为从 \(i\) 开始的权值为 \(i\) 的所有路中边数的最小值。
令 \(dis_i\) 为当前点 \(i\) 到 \(rt\) 的路径长度，\(cnt_i\) 为当前点 \(i\) 到 \(rt\) 的边数。
更新答案时，用当前子树 \(u\) 的 \(dis\) 和前面子树的桶来更新，即 \(ans=\min\limits_{v\in son_u}(ans,cnt_v+mn_{k-dis_v})\)。
const int N=2e6+5;
int n,k,siz[N],vis[N],rt,dp[N],sum,dis[N],d[N],cnt[N],c[N],tot,mn[N],ans;
vector<tuple<int,int>>G[N];
inline void getroot(int u,int fa){
siz[u]=1;dp[u]=0;
for(auto[v,w]:G[u])
if(v!=fa and !vis[v]){
getroot(v,u);
siz[u]+=siz[v];
dp[u]=max(dp[u],siz[v]);
}
dp[u]=max(dp[u],sum-siz[u]);
if(dp[u]<dp[rt])
rt=u;
}
inline void getdis(int u,int fa){
if(dis[u]>k)
return;
d[++tot]=dis[u];c[tot]=cnt[u];
for(auto[v,w]:G[u])
if(v!=fa and !vis[v]){
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
getdis(v,u);
}
}
inline void work(int u){
tot=0;mn[0]=0;
for(auto[v,w]:G[u])
if(!vis[v]){
int tmp=tot;
dis[v]=w;
cnt[v]=1;
getdis(v,u);
for(int i=tmp+1;i<=tot;i++)
ans=min(ans,mn[k-d[i]]+c[i]);
for(int i=tmp+1;i<=tot;i++)
mn[d[i]]=min(mn[d[i]],c[i]);
}
for(int i=1;i<=tot;i++)
mn[d[i]]=inf;
}
inline void solve(int u,int fa){
vis[u]=1;
work(u);
for(auto[v,w]:G[u])
if(v!=fa and !vis[v]){
sum=siz[v];rt=0;
getroot(v,u);
solve(rt,u);
}
}
signed main(){
sum=n=read();k=read();ans=inf;
for(int i=1;i<n;i++){
int u=read()+1,v=read()+1,w=read();
G[u].eb(mt(v,w));G[v].eb(mt(u,w));
}
dp[rt=0]=inf;
memset(mn,0x3f,sizeof(mn));
getroot(1,0);
solve(rt,0);
write((ans>=n)?-1:ans);
return 0;
}
P2634
todo.
边分治
todo.
点分树
todo.
标签：rt,路径,int,siz,分治,dp,dis From： https://www.cnblogs.com/QcpyWcpyQ/p/-/tree_divide