最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

2023.4.21【图论】点分治|世界新视野

来源：博客园

2023.4.21【图论】点分治

（点分治其实是广泛地统计树上全局路径问题的算法，此处采用luogu模板题的题面）

题目描述

给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。

  • 对于 \(100\%\) 的数据，保证 \(1 \leq n\leq 10^4\)，\(1 \leq m\leq 100\)，\(1 \leq k \leq 10^7\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^4\)。

算法描述

点分治，又名淀粉质，是计算树上路径问题的算法，与树剖不同的是，它计算的是对于整棵树的所有路径的情况，树剖难以完成。此题有\(m \leq 100\)个询问，我们考虑每一条路径，发现当我们枚举一个点\(x\)时，一条路径要么是经过\(x\)的，要么是与\(x\)不相交的。对于那些与x不相交的路径，我们可以向下分治来讨论。


(相关资料图)

我们发现，对于过x，但是同时经过x的父亲的路径，在\(x\)的父亲一层会考虑，所以我们只讨论\(x\)的子树以内的路径，遍历每一棵\(x\)的子树（直接连接的儿子），计算子树中每一个数到\(x\)的距离\(dis\)，将它们推进一个桶\(judge\)中，为了方便处理，我们将这个子树的点的\(dis\)在遍历时推进一个队列，我们扫描队列中的每个元素，如果\(judge[k_i - dis]\)是存在的，那么说明存在一条长为\(k\)的路径，从\(x\)先前的子树向上到\(x\)，再向下转到当前子树中的点，这个询问就有答案，鉴于询问数\(m \leq 100\)，直接枚举每个\(k_i\)，然后用\(O(1)\)判断每个\(k_i\)是否可以成立即可（这个地方开桶有一种空间换时间的思想）。对于每次清空\(judge\)数组，不能直接memset,要记录你更改了哪些值，再改回去就好了。

这是计算(calc)函数：

inline void calc(int x){    top = 0;    for(int i = head[x];i;i = e[i].next)    {        int to = e[i].v;        if(vis[to]) continue;        dis[to] = e[i].w;        rem[0] = 0;//rem[0]是计数器，rem是队列        getdis(to,x);        for(int j = 1;j <= rem[0];j++)            for(int k = 1;k <= m;k++)                if(query[k] - rem[j] >= 0)                    if(judge[query[k] - rem[j]] == 1)                        rt[k] = 1;        for(int j = 1;j <= rem[0];j++)            if(rem[j] <= T)                q[++top] = rem[j],judge[rem[j]] = 1;    }    for(int i = 1;i <= top;i++) judge[q[i]] = 0;}

时间复杂度\(O(nm\ logn)\)

讲解视频：https://www.bilibili.com/video/BV1GJ411x7h7

上条链不久被卡死了qwq

这里需要打破传统的树形问题的遍历顺序，而是每次处理一棵子树时，以这棵子树的重心为根进行处理，这样就能保证把子树切开后，大小一定会小于原来的\(\frac 12\)，所以就能保证复杂度严格，但是遍历顺序改变了，所以遍历过的点要将一个\(vis\)标签打为1，在所有函数的遍历中，如果\(vis_{son} = 1\)，就不访问\(son\)。

找重心部分：（一个点为根子树大小的最大值最小）

inline void dfs(int x,int last){siz[x] = 1;int now = 0;for(int i = head[x];i;i = e[i].next){int to = e[i].v;if(to == last || vis[to]) continue;dfs(to,x);siz[x] += siz[to];now = max(now,siz[to]);}now = max(now,sum - siz[x]);if(now < Minsiz) Minsiz = now,root = x;}

注意到一个细节：函数里面的“整棵树大小”用了一个\(sum\)变量，是因为每一次在子树中递归时总大小不一样，因为这次是确定了以x为根，下一次进入到儿子\(son\)中，就可以直接用\(siz_{son}\)作为\(sum\)。由于以\(son\)为根dfs时只会改变\(son\)子树的\(siz\)，所以对于\(x\)的其他子树没有影响。

Code

#includeusing namespace std;const int N = 1e5 + 5,T = 1e7 + 5;struct Edge{int v,w,next;}e[N * 5];int head[N],n,m,vis[N],dis[N],query[N],judge[N * 100],rt[N],siz[N],rem[N],root = 0,Minsiz = 0x3f3f3f3f,tot = 0,sum,q[N],top = 0;inline void add(int x,int y,int z){++tot;e[tot].v = y;e[tot].w = z;e[tot].next = head[x];head[x] = tot;}inline void dfs(int x,int last){siz[x] = 1;int now = 0;for(int i = head[x];i;i = e[i].next){int to = e[i].v;if(to == last || vis[to]) continue;dfs(to,x);siz[x] += siz[to];now = max(now,siz[to]);}now = max(now,sum - siz[x]);if(now < Minsiz) Minsiz = now,root = x;}inline void getdis(int x,int last){rem[++rem[0]] = dis[x];for(int i = head[x];i;i = e[i].next){int to = e[i].v;if(to == last || vis[to]) continue;dis[to] = dis[x] + e[i].w;getdis(to,x);}}inline void calc(int x){top = 0;for(int i = head[x];i;i = e[i].next){int to = e[i].v;if(vis[to]) continue;dis[to] = e[i].w;rem[0] = 0;getdis(to,x);for(int j = 1;j <= rem[0];j++)for(int k = 1;k <= m;k++)if(query[k] - rem[j] >= 0)if(judge[query[k] - rem[j]] == 1)rt[k] = 1;for(int j = 1;j <= rem[0];j++)if(rem[j] <= T)q[++top] = rem[j],judge[rem[j]] = 1;}for(int i = 1;i <= top;i++) judge[q[i]] = 0;}inline void solve(int x){judge[0] = 1;vis[x] = 1;calc(x);for(int i = head[x];i;i = e[i].next){int to = e[i].v;if(vis[to]) continue;sum = siz[to];Minsiz = 0x3f3f3f3f;dfs(to,0);solve(root);}}int main(){memset(siz,0,sizeof(siz));int x,y,z;cin>>n>>m;for(int i = 1;i <= n - 1;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}for(int i = 1;i <= m;i++) cin>>query[i];sum = n;dfs(1,0);memset(judge,0,sizeof(judge));memset(rt,0,sizeof(rt));memset(vis,0,sizeof(vis));solve(root);for(int i = 1;i <= m;i++)if(rt[i])cout<<"AYE"<

关键词：