学网站开发需要报培训机构吗,强化防疫指导,利用html做博客网站,淄博网站排名优化文章目录介绍#xff1a;题目#xff1a;做法#xff1a;模板题 [P3806 【模板】点分治1](https://www.luogu.com.cn/problem/P3806)代码#xff1a;介绍#xff1a;
将原问题分解成若干相同形式#xff0c;相互独立的子问题#xff0c;各个击破 一般用来解决有关树上路…
文章目录介绍题目做法模板题 [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.anssolve(T,rt)//统计答案(统计所有穿过化的路径) 3.对所有rt的子节点v递归调用work(v)
int work(u)
{rtfind_rt();//找到重心anssolve(rt);for v∈son[u]:answork(v)return ans;
}所有合法路径在上述分治过程中被不重不漏地统计到 详细过程 假设高度一共有h层经过h层递归后到达边界每一层子问题互不重叠 每一层都是O(N) 总复杂度O(H*N) 我们控制H的大小 H 递归的层数 点分治的复杂度被以下两个条件保证 1.hO(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 的点对是否存在。
代码
//niiick
#includeiostream
#includevector
#includealgorithm
#includequeue
#includecstring
#includecstdio
using namespace std;int read()
{int f1,x0;char ssgetchar();while(ss0||ss9){if(ss-)f-1;ssgetchar();}while(ss0ss9){xx*10ss-0;ssgetchar();}return f*x;
}const int inf10000000;
const int maxn100010;
int n,m;
struct node{int v,dis,nxt;}E[maxn1];
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].nxthead[u];E[tot].vv;E[tot].disdis;head[u]tot;
}void getrt(int u,int pa)//求重心
{size[u]1; maxp[u]0;for(int ihead[u];i;iE[i].nxt) {int vE[i].v;if(vpa||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]) rtu;
}void getdis(int u,int fa)//每一个子节点到根的距离
{rem[rem[0]]dis[u];for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vfa||vis[v])continue;dis[v]dis[u]E[i].dis;getdis(v,u);}
}void calc(int u)
{int p0;for(int ihead[u];i;iE[i].nxt){int vE[i].v;if(vis[v])continue;rem[0]0; dis[v]E[i].dis;getdis(v,u);//处理u的每个子树的disfor(int jrem[0];j;--j)//遍历当前子树的disfor(int k1;km;k)//遍历每个询问{if(query[k]rem[j])test[k]|judge[query[k]-rem[j]];//如果query[k]-rem[j]的路径存在就标记第k个询问}for(int jrem[0];j;--j)//保存出现过的dis于judge{q[p]rem[j];judge[rem[j]]1;}}for(int i1;ip;i)//处理完这个子树就清空judgejudge[q[i]]0;//特别注意一定不要用memeset会T}void solve(int u)
{ //judge[i]表示到根距离为i的路径是否存在vis[u]judge[0]1; calc(u);//处理以u为根的子树for(int ihead[u];i;iE[i].nxt)//对每个子树进行分治{int vE[i].v;if(vis[v])continue;sumsize[v]; maxp[rt0]inf;//注意sum是以v为根的子树大小getrt(v,0); solve(rt);//在子树中找重心并递归处理}
}int main()
{nread();mread();for(int i1;in;i){int uread(),vread(),disread();add(u,v,dis);add(v,u,dis);}for(int i1;im;i)query[i]read();//先记录每个询问以离线处理maxp[rt]sumn;//第一次先找整棵树的重心getrt(1,0); solve(rt);//对树进行点分治for(int i1;im;i){if(test[i]) printf(AYE\n);else printf(NAY\n);}return 0;
}
