点分治——树上路径统计

阅读量：6150 次

发布时间：2019-06-21

本文共 5050 字，大约阅读时间需要 16 分钟。

点分治：

一种分治的方法，一般用于（在不修改情况下），处理两点树上的两点之间的路径的问题。

每次从当前的子图中找到重心，即点分治“点”的含义。

以重心为当前的根节点，查找一切经过重心的路径，更新产生的贡献。

查找经过当前重心的路径的贡献，一般有两种方法：

1.树形背包思想

每次用当前子树和之前子树搭配找到贡献，然后把当前子树加入到之前子树集合中去。

为了计数的时候不重不漏，可以这样做：

把根（dis=0）加入集合。

之后就不断找子树，统计贡献，加入集合，直到子树循环完毕为止。

这样，既统计了根和子树的路径，也统计了子树之间跨根的路径。

2.容斥思想

我们每一层是要处理经过根的所有简单路径（这里是不经过重点重边）贡献。

一棵子树内部的点到根，再从根回到子树内部的路径一定不合法（一定有重边重点）。

我们可以先把所有的点的dis值依次和前面点统计、然后加入一个集合里。

但是这样显然会有上面的不合法的情况，所以，在这一次分治的最后，

循环每个子树，

把每个子树节点之间的两两贡献减去，方法同上（统计，加入集合）。

例题：

一、

模板题：

Description：

给定一棵有n个点的树

m次询问树上距离为k的点对是否存在。

Hint：

对于30%的数据n<=100

对于60%的数据n<=1000,m<=50

对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000

Solution：

在每一个区间里：div(x)表示，处理x所在的块的贡献。

个人比较喜欢用树形背包的思想，处理当前子树和之前子树结合产生的贡献。

0.开一个O（k）的数组exi，表示，距离根节点为k的点是否存在。

1.dfs1(x)找到子图的rt，用一个栈记录所有当前块的点。member

2.dfs2(x)找到子图的每个子树的dis，即到根的距离。再用一个栈记录访问的节点。

回溯时，如果x==rt，

①那么从栈里循环，找到another=k-dis[in[j]]表示，另一半需要的距离长度。

如果exi[another]=1，那么就找到了k

②之后，不断退栈，把exi[dis[in[j]]赋值为1。

注意，必须把所有的1的查找先进行完，再进行②的更新。因为是这个子树和之前子树的路径。

同一个子树之间的点在这一层不会产生贡献。

3.把member栈的元素不断退栈，把exi[dis[in[j]]赋值为0。保证之后再查到的路径一定是过rt'的合法路径。

4.封锁rt节点，之后不能再访问回来。

5.分治下去，找到没有“封锁”的点，令块大小totsz=sz[y]，div(y)

最后也不用判断totsz==1，一定全部会把回路都封锁住。直接就返回了。

代码：

注意：1.dis[in[j]]可能大于k，就RE；

2.another可能小于0，又RE

#include
      
       using namespace std;const int N=10000+10;const int M=10000000+3;const int inf=0x3f3f3f3f;int n,m;int k;//Kbool exi[M];int sta[N],top;//stack to memorize exiint in[N],up;//stack to memorize dfs2struct node{    int nxt,to;    int val;    }e[2*N];int hd[N],cnt;void add(int x,int y,int z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].val=z;    hd[x]=cnt;}int dis[N];int rt;bool no[N];int sz[N];int mxs[N];int minsize;int totsz;bool fl;//find ?void dfs1(int x,int fa){    sz[x]=1;    for(int i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(no[y]) continue;        if(y==fa) continue;        dfs1(y,x);        sz[x]+=sz[y];        mxs[x]=max(mxs[x],sz[y]);    }    mxs[x]=max(mxs[x],totsz-sz[x]);    if(minsize>mxs[x]){        minsize=mxs[x];        rt=x;    }}void dfs2(int x,int fa,int d){    dis[x]=d;    in[++up]=x;    for(int i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(no[y]) continue;        if(y==fa) continue;        dfs2(y,x,d+e[i].val);        if(x==rt){            int kk=up;            while(kk){                int ano=k-dis[in[kk]];                if(ano>=0&&ano<=k){                    if(exi[ano]) fl=true;                }                 kk--;            }            while(in[up]!=rt){                sta[++top]=in[up];                if(dis[sta[top]]<=k) exi[dis[sta[top]]]=1;                up--;            }        }    }}void div(int x){    if(fl) return;    up=0;top=0;    minsize=inf;    dfs1(x,0);//find rt    sta[++top]=rt;    exi[0]=1;    dfs2(rt,0,0);    while(top){        if(dis[sta[top]]<=k) exi[dis[sta[top]]]=0;        dis[sta[top]]=0;        mxs[sta[top]]=0;                top--;    }    no[rt]=1;    for(int i=hd[rt];i;i=e[i].nxt){        int y=e[i].to;        if(no[y]) continue;        totsz=sz[y];        div(y);    }}int main(){    scanf("%d%d",&n,&m);    int x,y,z;    for(int i=1;i<=n-1;i++){        scanf("%d%d%d",&x,&y,&z);        add(x,y,z);add(y,x,z);    }    for(int i=1;i<=m;i++){        scanf("%d",&k);        fl=false;        totsz=n;        minsize=inf;        memset(mxs,0,sizeof mxs);        memset(dis,0,sizeof dis);        memset(no,0,sizeof no);        memset(sz,0,sizeof sz);        div(1);        if(fl) printf("AYE\n");        else printf("NAY\n");    }    return 0;}

模板

二、

[国家集训队]聪聪可可

题目描述

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输出格式：

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

【数据规模】

对于100%的数据，n<=20000。

Solution：

框架大致同上。

统计子树里mod 3=0 mod3=1 mod3=2的点的个数。

再用一个sum[3]表示，之前所有的子树点里mod3余数的点的个数。

每次rt回溯的时候，更新：ans+=sum[0]*sub[y][0],ans+=sum[1]*sub[y][2],ans+=sum[2]*sub[y][1]

然后跟新sum

只需要一个栈，存储member就可以。sub可以dp得到。

Code：

#include
         
          using namespace std;const int N=20000+10;const int inf=0x3f3f3f3f;int n;int gcd(int a,int b){    return b?gcd(b,a%b):a;}struct node{    int nxt,to,val;}e[2*N];int hd[N],cnt;int rt;void add(int x,int y,int z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    e[cnt].val=z;    hd[x]=cnt;}int ans;int sum[3],sub[N][3];int dis[N],sz[N],mxs[N];bool vis[N];int totsz,minsz;int sta[N],top;void dfs1(int x,int fa){    sz[x]=1;sta[++top]=x;    for(int i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(y==fa) continue;        if(vis[y]) continue;        dfs1(y,x);        sz[x]+=sz[y];        mxs[x]=max(mxs[x],sz[y]);    }    mxs[x]=max(mxs[x],totsz-sz[x]);    if(mxs[x]

聪聪可可