点分治复习笔记

点分治

学习笔记

总：点分治是处理树上问题的一个比较好用的工具，时间复杂度是$O(nlogn)$级别的，非常优秀。其实感觉非常的暴力，但是它还跑得很快。。。

点分标准函数：

　　$find-rt(int;x,int;fa)$:用于寻找在$x$所在的子树中的重心

　　$work(int;u)$:$u$表示本棵子树的重心，也就是说要处理$u$为重心的这棵子树的信息，是点分中的主函数。

　　$dfs(in;u,int;fa)$: 这是一个普通的搜索，一般用它来搜出子树中所有路径，用于处理路径信息。

　　$solve(int;u)$: 用于合并路径信息，以及统计答案。

点分能处理的问题：主要是路径问题吧，还有树上连通块问题。

点分的基本思路：

　　就如它的名字一样，本质上是一个分治。每次都对一个子问题来求解，也就是说$work()$函数每次面对的是一棵子树的信息，最初的树就是原树。

　　1.找到重心，然后以重心作为分界点，将目前的树分为若干个子树，继续分治处理。

　　2.在每一次遇到一棵树的时候，都要用$dfs$搜出所有以重心开始的路径(注意要在本棵子树内)，然后用$solve()$合并。

　　注意它和树形dp的区别在于它几乎不做上传，也就是说，它每次处理问题都是独立的。

例题

P3806 【模板】点分治1

题目大意：

给定一棵有n个点的树

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

题解：

点分模板题，点分能处理的标准问题。就是要把点分的函数都一个一个实现一下。

首先是寻找重心

 1 void find_rt(int u,int fa){
 2     siz[u]=1;
 3     int t,vv;
 4     t=indexx[u];
 5     while(t){
 6         vv=edge[t].v;
 7         if(vv!=fa && !vist[vv]){
 8             find_rt(vv,u);
 9             siz[u]+=siz[vv];
10             f[u]=max(f[u],siz[vv]);
11         }
12         t=edge[t].nxt;
13     }
14     f[u]=max(f[u],sum-siz[u]);
15     if(f[u]<f[rt]) rt=u;
16 }

注意$f[0]$要赋成$INF$。

具体来说就是找出当前子树里一个点使它的最重子树尽可能轻，$f[u]$ 表示$u$最重子树的重量，那个$vist$数组是防止它搜出当前树的。

然后是点分主函数$work()$

 1 void work(int u){
 2     vist[u]=1;
 3     solve(u,0,1);
 4     int t,vv;
 5     t=indexx[u];
 6     while(t){
 7         vv=edge[t].v;
 8         if(!vist[vv]){
 9             solve(vv,edge[t].q*2,-1);
10             sum=siz[vv];
11             rt=0;
12             find_rt(vv,u);
13             work(rt);
14         }
15         t=edge[t].nxt;
16     }
17 }

这个就是分治的主函数了。每次进入该树之后进行$solve()$第二个$solve()$是为了去重，因为可能两条路径有重叠部分，所以需要把重叠部分减掉。然后在子树中继续分治，先找重心，然后继续递归。

然后是处理部分$solve()$

 1 void solve(int u,int alr,int type){
 2     tot=0;
 3     dfs(u,0,0);
 4     sort(dist+1,dist+tot+1);
 5     int l=1,r=tot;
 6     for(int i=1;i<=m;i++){
 7         l=1,r=tot;
 8         while(l<r){
 9             if(dist[l]+dist[r]+alr<Q[i]) l++;
10             else if(dist[l]+dist[r]+alr==Q[i]){
11                 int tl=l;
12                 for(;dist[l]==dist[tl]&&tl<r;tl++) al[i]+=0;
13                 int tr=r;
14                 for(;dist[r]==dist[tr]&&tr>=tl;tr--) al[i]+=(tl-l)*type;
15                 r=tr;l=tl;
16             }
17             else r--;
18         }
19     }
20 }

先用$dfs()$搜出本棵子树里以$u$为起点的所有路径，然后用双指针合并。那个$alr$是为了去重使用的，中间诡异的$tl$和$tr$是因为可能会有长度一样的。

然后就是$dfs()$了

 1 void dfs(int u,int fa,int dep){
 2     int t,vv,qq;
 3     t=indexx[u];
 4     dist[++tot]=dep;
 5     while(t){
 6         vv=edge[t].v;
 7         qq=edge[t].q;
 8         if(!vist[vv] && vv!=fa){
 9             dfs(vv,u,dep+qq);
10         }
11         t=edge[t].nxt;
12     }
13 }

这个不解释应该也能看懂吧，就是搜出所有路径长度存在$dist[]$里。

那么这道题就做完了，点分的套路大概就是这样。这道题是用的容斥去重，也可以分不同的儿子进行讨论那样的，实现起来也差不多，但我感觉分儿子讨论的那个更直观一些，这个更好写一些。

最后贴代码。（我的链式前向星写的比较奇怪，大家就理解一下$vv$是它的儿子就行了）（$define;int;long;long$大法好啊）

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define N 20011
#define int long long
using namespace std;
int siz[N],sum,al[N],dist[N],vist[N],indexx[N],rt,f[N],tot,n,m,Q[N],cnt;
struct apple{
    int v,nxt,q;
}edge[N*4];
void addedge(int x ,int y,int z){
    edge[++cnt].v=y;
    edge[cnt].q=z;
    edge[cnt].nxt=indexx[x];
    indexx[x]=cnt;
} 
void find_rt(int u,int fa){
    siz[u]=1;
    int t,vv;
    t=indexx[u];
    while(t){
        vv=edge[t].v;
        if(vv!=fa && !vist[vv]){
            find_rt(vv,u);
            siz[u]+=siz[vv];
            f[u]=max(f[u],siz[vv]);
        }
        t=edge[t].nxt;
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt]) rt=u;
}
void dfs(int u,int fa,int dep){
    int t,vv,qq;
    t=indexx[u];
    dist[++tot]=dep;
    while(t){
        vv=edge[t].v;
        qq=edge[t].q;
        if(!vist[vv] && vv!=fa){
            dfs(vv,u,dep+qq);
        }
        t=edge[t].nxt;
    }
}
void solve(int u,int alr,int type){
    tot=0;
    dfs(u,0,0);
    sort(dist+1,dist+tot+1);
    int l=1,r=tot;
    for(int i=1;i<=m;i++){
        l=1,r=tot;
        while(l<r){
            if(dist[l]+dist[r]+alr<Q[i]) l++;
            else if(dist[l]+dist[r]+alr==Q[i]){
                int tl=l;
                for(;dist[l]==dist[tl]&&tl<r;tl++) al[i]+=0;
                int tr=r;
                for(;dist[r]==dist[tr]&&tr>=tl;tr--) al[i]+=(tl-l)*type;
                r=tr;l=tl;
            }
            else r--;
        }
    }
}
void work(int u){
    vist[u]=1;
    solve(u,0,1);
    int t,vv;
    t=indexx[u];
    while(t){
        vv=edge[t].v;
        if(!vist[vv]){
            solve(vv,edge[t].q*2,-1);
            sum=siz[vv];
            rt=0;
            find_rt(vv,u);
            work(rt);
        }
        t=edge[t].nxt;
    }
}
signed main(){
//    freopen("testdata.in","r",stdin);
    int x,y,z;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<n;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        addedge(x,y,z);
        addedge(y,x,z);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld",&Q[i]);
    }
//    sort(Q+1,Q+m+1,less<int>());
    f[0]=200000000;
    sum=n;
    rt=0;
    find_rt(1,0);
    work(rt);
    for(int i=1;i<=m;i++){
        if(al[i]) printf("AYE
");
        else printf("NAY
");
    }
    return 0;
}

View Code

BZOJ2599 [IOI2011]Race

题意：

给一棵树，每条边有权。求一条简单路径，权值和等于$K$，且边的数量最小。

题解：

依旧是点分标准操作。

但是发现它求的不是总数，而是最值，所以用去重法可能会比较麻烦吧。由于$K$的值用数组开得下，在这里用的是分不同儿子的方法。

每次在$dfs$的时候就顺便统计了答案，在遍历完重心的一个儿子子树后再把它的信息推入到$hashh$数组中，这样在更新的时候用的$hashh$值代表的链一定和本条链没有重叠部分，这样就可以直接统计答案了。

每次注意清$hashh$，注意不要$memset$。

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <stack>
  6 #define N 200011
  7 #define INF 0x7f7f7f7f
  8 using namespace std;
  9 struct apple{
 10     int v,nxt,q;
 11 }edge[N*2];
 12 int indexx[N],siz[N],f[N],deep[N],dist[N],hashh[N*10],n,k,ans=INF,tot,vist[N],sum,rt;
 13 stack<int> pq,Q;
 14 void addedge(int x,int y,int z){
 15     edge[++tot].v=y;
 16     edge[tot].nxt=indexx[x];
 17     edge[tot].q=z;
 18     indexx[x]=tot;
 19 }
 20 void find_root(int x,int fa){
 21     siz[x]=1;
 22     f[x]=0;
 23     int t,vv;
 24     t=indexx[x];
 25     while(t){
 26         vv=edge[t].v;
 27         if(!vist[vv] && vv!=fa){
 28             find_root(vv,x);
 29             siz[x]+=siz[vv];
 30             f[x]=max(f[x],siz[vv]);
 31         }
 32         t=edge[t].nxt;
 33     }
 34     f[x]=max(f[x],sum-siz[x]);
 35     if(f[x]<f[rt]) rt=x;
 36 }
 37 void dfs(int u,int fa,int ancestor){
 38     if(k>=dist[u]){
 39         ans=min(ans,deep[u]+hashh[k-dist[u]]);
 40     }
 41     int t=indexx[u],vv,x;
 42     while(t){
 43         vv=edge[t].v;
 44         if(!vist[vv] && vv!=fa){
 45             dist[vv]=dist[u]+edge[t].q;
 46             deep[vv]=deep[u]+1;
 47             pq.push(vv);
 48             dfs(vv,u,ancestor);
 49         }
 50         t=edge[t].nxt;
 51     }
 52     if(fa==ancestor){
 53         x=pq.top();
 54         pq.pop();
 55         if(dist[x]<=k){
 56             hashh[dist[x]]=min(hashh[dist[x]],deep[x]);
 57             Q.push(dist[x]);
 58         }
 59         while(x!=u){
 60             x=pq.top();
 61             pq.pop();
 62             if(dist[x]<=k){
 63                 hashh[dist[x]]=min(hashh[dist[x]],deep[x]);
 64                 Q.push(dist[x]);
 65             }
 66         }
 67     }
 68 }
 69 void Clear(){
 70     int x;
 71     while(!Q.empty()){
 72         x=Q.top();
 73         Q.pop();
 74         hashh[x]=INF;
 75     }
 76 }
 77 void work(int now){
 78     dist[now]=0;
 79     deep[now]=0;
 80     vist[now]=1;
 81     dfs(now,0,now);
 82     ans=min(ans,hashh[k]);
 83     Clear();
 84     int t=indexx[now],vv;
 85     while(t){
 86         vv=edge[t].v;
 87         if(!vist[vv]){
 88             rt=0;
 89             sum=siz[vv];
 90             find_root(vv,0);
 91             work(rt);
 92         }
 93         t=edge[t].nxt;
 94     }
 95 }
 96 int main(){
 97     int x,y,z;
 98     scanf("%d%d",&n,&k);
 99     sum=n;
100     for(int i=1;i<n;i++){
101         scanf("%d%d%d",&x,&y,&z);
102         x++;y++;
103         addedge(x,y,z);
104         addedge(y,x,z);
105     }
106     memset(hashh,0x7f,sizeof(hashh));
107     f[0]=INF;
108     rt=0;
109     find_root(1,0);
110     work(rt);
111     if(ans==INF) printf("-1");
112     else printf("%d",ans);
113     return 0;
114 }

View Code

P2634 [国家集训队]聪聪可可

题意：

给出一棵树，边有边权，求两人分别独立任选一个点后两点之间简单路径边权和是3的倍数的概率。

题解：

点分，又是点分。直接水过~。把$dp[i]$与$dp[3-i-alr]$乘起来就行了，由于两个人是独立操作的，所以可能选到同一个点的。这么写再加去重写法就可以了。分母是$n*n$，约分即可。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define N 20011
using namespace std;
int siz[N],n,indexx[N],f[N],tot,hashh[4],ans,vist[N],sum,Stack[N],top,rt;
struct apple{
    int v,nxt,q;
}edge[N*4];
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].q=z;
    edge[tot].nxt=indexx[x];
    indexx[x]=tot;
}
void find_rt(int u,int fa){
    int t,vv;
    siz[u]=1;
    f[u]=0;
    t=indexx[u];
    while(t){
        vv=edge[t].v;
        if(!vist[vv] && vv!=fa){
            find_rt(vv,u);
            siz[u]+=siz[vv];
            f[u]=max(f[u],siz[vv]);
        }
        t=edge[t].nxt;
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt]) rt=u;
}
void dfs(int u,int fa,int dep){
    Stack[++top]=dep;
    int t,vv;
    t=indexx[u];
    while(t){
        vv=edge[t].v;
        if(!vist[vv] && vv!=fa){
            dfs(vv,u,dep+edge[t].q);
        }
        t=edge[t].nxt;
    }
}
int solve(int u,int alr){
    int ret=0;
    alr%=3;
    top=0;
    dfs(u,0,0);
    hashh[0]=hashh[1]=hashh[2]=0;
    for(int i=1;i<=top;i++){
        hashh[Stack[i]%3]++;
    }
    for(int i=0;i<=2;i++){
        ret+=hashh[i]*hashh[(30-i-alr)%3];
    }
    return ret;
}
void work(int u){
    ans+=solve(u,0);
    vist[u]=1;
    int t,qq,vv;
    t=indexx[u];
    while(t){
        vv=edge[t].v;
        qq=edge[t].q;
        if(!vist[vv]){
            ans-=solve(vv,qq*2);
            rt=0;
            sum=siz[vv];
            find_rt(vv,u);
            work(rt);
        }
        t=edge[t].nxt;
    }
}
int main(){
    int x,y,z;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
        addedge(y,x,z);
    }
    sum=n;
    rt=0;
    f[0]=200000000;
    find_rt(1,0);
    work(rt);
    int p=n*n;
    int tmp=gcd(p,ans);
    p/=tmp;
    ans/=tmp;
    printf("%d/%d",ans,p);
    return 0;
}

聪聪可可

P2993 [FJOI2014]最短路径树问题

题意：

给一个无向连通图，要求求一个字典序最小的最短路树，然后求最长的包含K个点的简单路径长度、长度为该最长长度的不同路径条数。

题解：

和Race那题比较像吧，一样的方法水过~

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <queue>
  8 #include <stack>
  9 #define X 0
 10 #define Y 1
 11 #define Z 2
 12 #define N 60011
 13 using namespace std;
 14 int f[N],siz[N],dist[N],ee[N][3],n,m,used[N],hashh[N],rt,vist[N],indexx[N],tot,sum,k,deep[N],ans;
 15 int cnt,has[N];
 16 struct node{
 17     int y,z,no;
 18     bool operator<(const node &other)const{
 19         return y<other.y;
 20     }
 21     node(int yy,int zz,int nn){
 22         y=yy;
 23         z=zz;
 24         no=nn;
 25     }
 26     node(){}
 27 };
 28 struct apple{
 29     int no,dist,pre;
 30     bool operator<(const apple &other)const{
 31         return dist>other.dist;
 32     }
 33 }temp;
 34 struct point{
 35     int v,nxt,q;
 36 }edge[N*2];
 37 priority_queue<apple> pq;
 38 vector<node> Map[N];
 39 stack<int> pp,Q;
 40 void addedge(int x,int y,int z){
 41     edge[++tot].v=y;
 42     edge[tot].q=z;
 43     edge[tot].nxt=indexx[x];
 44     indexx[x]=tot;
 45 }
 46 void dij(){
 47     int x,vv,qq;
 48     x=1;
 49     temp.no=1;
 50     dist[1]=0;
 51     temp.dist=0;
 52     pq.push(temp);
 53     while(!pq.empty()){
 54         temp=pq.top();
 55         pq.pop();
 56         x=temp.no;
 57         if(vist[x]) continue;
 58         used[temp.pre]=1;
 59         vist[x]=1;
 60         for(int i=0;i<Map[x].size();i++){
 61             vv=Map[x][i].y;
 62             qq=Map[x][i].z;
 63             if(dist[vv]>dist[x]+qq){
 64                 dist[vv]=dist[x]+qq;
 65                 temp.no=vv;
 66                 temp.dist=dist[vv];
 67                 temp.pre=Map[x][i].no;
 68                 pq.push(temp);
 69             }
 70         }
 71     }
 72 }
 73 void find_root(int x,int fa){
 74     siz[x]=1;
 75     f[x]=0;
 76     int t=indexx[x],vv;
 77     while(t){
 78         vv=edge[t].v;
 79         if(!vist[vv] && vv!=fa){
 80             find_root(vv,x);
 81             siz[x]+=siz[vv];
 82             f[x]=max(f[x],siz[vv]);
 83         }
 84         t=edge[t].nxt;
 85     }
 86     f[x]=max(f[x],sum-siz[x]);
 87     if(f[x]<f[rt]) rt=x;
 88 }
 89 void dfs(int u,int fa,int ancestor){
 90     int ta;
 91     if(k>=deep[u] && hashh[k-deep[u]+1]){
 92         if(hashh[k-deep[u]+1]+dist[u]==ans) cnt+=has[k-deep[u]+1];
 93         else if(hashh[k-deep[u]+1]+dist[u]>ans){
 94             ans=hashh[k-deep[u]+1]+dist[u];
 95             cnt=has[k-deep[u]+1];
 96         }
 97     }
 98     int t=indexx[u],vv,qq,x;
 99     while(t){
100         vv=edge[t].v;
101         qq=edge[t].q;
102         if(!vist[vv] && vv!=fa){
103             dist[vv]=dist[u]+qq;
104             deep[vv]=deep[u]+1;
105             pp.push(vv);
106             dfs(vv,u,ancestor);
107         }
108         t=edge[t].nxt;
109     }
110     if(fa==ancestor){
111         x=pp.top();
112         pp.pop();
113         if(deep[x]<=k){
114             if(dist[x]==hashh[deep[x]]) has[deep[x]]++;
115             else if(dist[x]>hashh[deep[x]]){
116                 hashh[deep[x]]=dist[x];
117                 has[deep[x]]=1;
118             }
119             Q.push(deep[x]);
120         }
121         while(x!=u){
122             x=pp.top();
123             pp.pop();
124             if(deep[x]<=k){
125                 if(dist[x]==hashh[deep[x]]) has[deep[x]]++;
126                 else if(dist[x]>hashh[deep[x]]){
127                     hashh[deep[x]]=dist[x];
128                     has[deep[x]]=1;
129                 }
130                 Q.push(deep[x]);
131             }
132         }
133     }
134 }
135 void Clear(){
136     int x;
137     while(!Q.empty()){
138         x=Q.top();
139         Q.pop();
140         hashh[x]=0;
141         has[x]=0;
142     }
143 }
144 void work(int now){
145     dist[now]=0;
146     deep[now]=1;
147     vist[now]=1;
148     dfs(now,0,now);
149     if(ans==hashh[k]) cnt+=has[k];
150     else if(ans<hashh[k]){
151         ans=hashh[k];
152         cnt=has[k];
153     }
154     Clear();
155     int t=indexx[now],vv;
156     while(t){
157         vv=edge[t].v;
158         if(!vist[vv]){
159             rt=0;
160             sum=siz[vv];
161             find_root(vv,0);
162             work(rt);
163         }
164         t=edge[t].nxt;
165     }
166 }
167 int main(){
168     int x,y,z;
169     scanf("%d%d%d",&n,&m,&k);
170     for(int i=1;i<=m;i++){
171         scanf("%d%d%d",&x,&y,&z);
172         ee[i][X]=x;
173         ee[i][Y]=y;
174         ee[i][Z]=z;
175         Map[x].push_back(node(y,z,i));
176         Map[y].push_back(node(x,z,i));
177     }
178     for(int i=1;i<=n;i++){
179         sort(Map[i].begin(),Map[i].end());
180     }
181     memset(dist,127,sizeof(dist));
182     dij();
183     memset(vist,0,sizeof(vist));
184     memset(dist,0,sizeof(dist));
185     for(int i=1;i<=m;i++){
186         if(used[i]){
187             addedge(ee[i][X],ee[i][Y],ee[i][Z]);
188             addedge(ee[i][Y],ee[i][X],ee[i][Z]);
189         }
190     }
191     sum=n;
192     rt=0;
193     f[0]=2000000000;
194     find_root(1,0);
195     work(rt);
196     printf("%d %d",ans,cnt);
197     return 0;
198 }

最短路径树

P3727 曼哈顿计划E

题意：

给出一棵树，点有点权，给出一种博弈方式，问存不存在一条链，使在该链上博弈时，先手必败。

题解：

博弈上树。首先你需要会一些基本博弈，并打表发现它们的规律。写出一个$Get-SG$函数。（打表真费劲）

 1 int get_SG(int x,int op){
 2     if(op==1) return x;
 3     else if(op==2){
 4         if(s%2==1) return x%2;
 5         else{
 6             int len=s+1;
 7             x%=len;if(x==0) x=len;
 8             if(x<=len-2) return x%2;
 9             else if(x==len-1) return 2;
10             else return 0;
11         }
12     }
13     else if(op==3){
14         return x/s;
15     }
16     else if(op==4){
17         if(x==0) return 0;
18         else if(x%4==1 || x%4==2) return x;
19         else if(x%4==3) return x+1;
20         else return x-1;
21     }
22 }

然后就可以重赋点权为该点的$SG$值了，这样问题就转变为了是否存在一条链，使得点权异或和为0。发现点权太大数组存不下，所以考虑挂链hash。然后就结束了

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cstdio>
  5 #define N 60011
  6 #define MAX 1313131
  7 #define int long long
  8 using namespace std;
  9 int val[N],dp[N],n,tot,indexx[N],s,siz[N],f[N],rt,sum,vist[N],dist[N],cnt,ans,ind[MAX*2],tt;
 10 struct apple{
 11     int v,nxt,cnt;
 12 }edge[N*4],ee[N*4];
 13 inline int read(){
 14     int ret=0,f=1;char ch=getchar();
 15     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 16     while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
 17     return ret;
 18 }
 19 void add_to_hash(int x){
 20     ee[++tt].v=x;
 21     ee[tt].nxt=ind[x%MAX];
 22     ee[tt].cnt=1;
 23     ind[x%MAX]=tt;
 24 }
 25 int find_hash(int x){
 26     int t=ind[x%MAX],vv,ret=0;
 27     while(t){
 28         vv=ee[t].v;
 29         if(vv==x){
 30             return ee[t].cnt;
 31         }
 32         t=ee[t].nxt;
 33     }
 34     return 0;
 35 }
 36 void addedge(int x,int y){
 37     edge[++tot].v=y;
 38     edge[tot].nxt=indexx[x];
 39     indexx[x]=tot;
 40 }
 41 int get_SG(int x,int op){
 42     if(op==1) return x;
 43     else if(op==2){
 44         if(s%2==1) return x%2;
 45         else{
 46             int len=s+1;
 47             x%=len;if(x==0) x=len;
 48             if(x<=len-2) return x%2;
 49             else if(x==len-1) return 2;
 50             else return 0;
 51         }
 52     }
 53     else if(op==3){
 54         return x/s;
 55     }
 56     else if(op==4){
 57         if(x==0) return 0;
 58         else if(x%4==1 || x%4==2) return x;
 59         else if(x%4==3) return x+1;
 60         else return x-1;
 61     }
 62 }
 63 void find_rt(int u,int fa){
 64     siz[u]=1;
 65     int t,vv;
 66     f[u]=0;
 67     t=indexx[u];
 68     while(t){
 69         vv=edge[t].v;
 70         if(!vist[vv] && vv!=fa){
 71             find_rt(vv,u);
 72             siz[u]+=siz[vv];
 73             f[u]=max(f[u],siz[vv]);
 74         }
 75         t=edge[t].nxt;
 76     }
 77     f[u]=max(f[u],sum-siz[u]);
 78     if(f[u]<f[rt]) rt=u;
 79 }
 80 void dfs(int u,int fa,int dep){
 81     dist[++cnt]=dep;
 82     int t,vv;
 83     t=indexx[u];
 84     while(t){
 85         vv=edge[t].v;
 86         if(vv!=fa && vist[vv]==0){
 87             dfs(vv,u,dep^dp[vv]);
 88         }
 89         t=edge[t].nxt;
 90     }
 91 }
 92 inline int solve(int u,int x){
 93     int ret=0;
 94     cnt=0;
 95     dfs(u,0,0);
 96     tt=0;
 97     for(int i=2;i<=cnt;i++){
 98         if(find_hash(dist[i]^x)){
 99             int t,vv;
100             t=ind[(dist[i]^x)%MAX];
101             while(t){
102                 vv=ee[t].v;
103                 if(vv==(dist[i]^x)){
104                     edge[t].cnt++;
105                     break;
106                 }
107                 t=ee[t].nxt;
108             }
109         }
110         else add_to_hash(dist[i]^x);
111     }
112     for(int i=2;i<=cnt;i++){
113         ret+=find_hash(dist[i]);
114     }tot=0;
115     for(int i=2;i<=cnt;i++){
116         ind[(dist[i]^x)%MAX]=0;
117     }
118     return ret;
119 }
120 void work(int u){
121     vist[u]=1;
122     ans+=solve(u,dp[u]);
123     int t,vv;
124     t=indexx[u];
125     while(t){
126         vv=edge[t].v;
127         if(!vist[vv]){
128             ans-=solve(vv,dp[u]);
129             sum=siz[vv];
130             rt=0;
131             find_rt(vv,u);
132             work(rt);
133         }
134         t=edge[t].nxt;
135     }
136 }
137 signed main(){
138     int op,T,x,y;
139     T=read();
140     while(T--){
141         memset(indexx,0,sizeof(indexx));tot=0;
142         ans=0;
143         memset(vist,0,sizeof(vist));
144         n=read();
145         for(int i=1;i<n;i++){
146             x=read();y=read();
147             addedge(x,y);
148             addedge(y,x);
149         }
150         for(int i=1;i<=n;i++){
151             val[i]=read();
152         }
153         op=read();
154         if(op==2 || op==3) s=read();
155         for(int i=1;i<=n;i++){
156             dp[i]=get_SG(val[i],op);
157         }
158         f[0]=0x7ffffffffffff;
159         rt=0;
160         sum=n;
161         find_rt(1,0);
162         work(rt);
163         if(ans) printf("Mutalisk ride face how to lose?
");
164         else printf("The commentary cannot go on!
");
165     }
166     return 0;
167 }

曼哈顿计划E

P4886 快递员

题意：

给出一棵树，有边权。给出若干个点对$(x,y)$，要求找出一个点$u$，使得对于所有给出点对$dist(x,u)+dist(y,u)$的最大值最小，输出那个最大值的最小值。

题解：

终于不是套路题了。这道题还有点意思，首先还是要点分，算出u为该点时所有点对的答案（由两条链拼起来）。然后考虑一下在什么情况下答案不可以更优：

1.最大值由出现于两颗不同子树的链拼起来得到。这样如果我们移动$u$的话，不管是向$x$方向还是向$y$方向，都会导致一条链变长，一条链变短，总长不变。如果向其他方向移动的话一定更不优。

2.最大值有多组，且它们不位于同一棵子树内。同理也是，不管向哪个方向移动都会使至少一个链组增长，变得更大。

这两种情况可以直接输出答案。除了这两种情况的话就还剩下每组最大值的两条链都出现同一棵子树里，那么我们只要把$u$移向那个子树方向中的重心就行了。

感觉还是有点意思，比花式模板要强一些。注意如果有一个端点在$u$点的情况，也算到不同子树里。

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <vector>
  5 #define N 100011
  6 #define INF 0x7f7f7f7f
  7 using namespace std;
  8 struct apple{
  9     int v,nxt,q;
 10 }edge[N*4];
 11 int indexx[N],vist[N],dist[N],col[N],n,m,Q[N][2],tot,f[N],sum,siz[N],rt,used[N],ans=INF;
 12 void addedge(int x,int y,int z){
 13     edge[++tot].v=y;
 14     edge[tot].q=z;
 15     edge[tot].nxt=indexx[x];
 16     indexx[x]=tot;
 17 }
 18 void find_rt(int u,int fa){
 19     int t,vv;
 20     t=indexx[u];
 21     f[u]=0;siz[u]=1;
 22     while(t){
 23         vv=edge[t].v;
 24         if(!vist[vv] && vv!=fa){
 25             find_rt(vv,u);
 26             siz[u]+=siz[vv];
 27             f[u]=max(f[u],siz[vv]);
 28         }
 29         t=edge[t].nxt;
 30     }
 31     f[u]=max(f[u],sum-siz[u]);
 32     if(f[u]<f[rt]) rt=u;
 33 }
 34 void dfs(int u,int fa,int c){
 35     if(fa==0) c=0; 
 36     int t,vv;
 37     col[u]=c;
 38     t=indexx[u];
 39     while(t){
 40         vv=edge[t].v;
 41         if(vv!=fa){
 42             dist[vv]=dist[u]+edge[t].q;
 43             if(fa==0) c++;
 44             dfs(vv,u,c);
 45         }
 46         t=edge[t].nxt;
 47     }
 48 }
 49 int solve(int u,int &maxx){
 50     int cnt=0,k=0;
 51     maxx=0;
 52     dist[u]=0;
 53     dfs(u,0,0);
 54     for(int i=1;i<=m;i++){
 55         int x=Q[i][0];
 56         int y=Q[i][1];
 57         used[i]=0;
 58         if(dist[x]+dist[y]>maxx){
 59             maxx=dist[x]+dist[y];
 60             used[i]=++cnt;
 61         }
 62         else if(dist[x]+dist[y]==maxx){
 63             used[i]=cnt;
 64         }
 65     }
 66     for(int i=1;i<=m;i++){
 67         int x=Q[i][0];
 68         int y=Q[i][1];
 69         if(used[i]==cnt){
 70             if(col[x]!=col[y]) return -1;
 71             else if(k && col[x]!=k) return -1;
 72             k=col[x];
 73         }
 74     }
 75     return k;
 76 }
 77 void work(int u){
 78     vist[u]=1;
 79     int maxx=0,t=indexx[u],vv;
 80     int k=solve(u,maxx);
 81     ans=min(ans,maxx);
 82     while(t){
 83         vv=edge[t].v;
 84         if(col[vv]==k && !vist[vv]){
 85             rt=0;sum=siz[vv];
 86             find_rt(vv,u);
 87             work(rt);
 88         }
 89         t=edge[t].nxt;
 90     }
 91 }
 92 int main(){
 93     int x,y,z;
 94     scanf("%d%d",&n,&m);
 95     for(int i=1;i<n;i++){
 96         scanf("%d%d%d",&x,&y,&z);
 97         addedge(x,y,z);
 98         addedge(y,x,z);
 99     }
100     for(int i=1;i<=m;i++){
101         scanf("%d%d",&x,&y);
102         Q[i][0]=x;
103         Q[i][1]=y;
104     }
105     rt=0;f[0]=INF;
106     sum=n;
107     find_rt(1,0);
108     work(rt);
109     printf("%d",ans);
110     return 0;
111 }

快递员

P3714 [BJOI2017]树的难题

题意：

给你一棵 n 个点的无根树。

树上的每条边具有颜色。一共有 m 种颜色，编号为 1 到 m。第 i 种颜色的权值为 ci。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划分成若干个相同颜色段。

定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

计算经过边数在 l 到 r 之间的所有简单路径中，路径权值的最大值。

题解：

这道题也没那么模板。挺有意思的，加了一个颜色限制，加了一个长度限制。

可以有感觉，这个在处理的时候肯定不能用去重写法，所以我们考虑分开儿子讨论。

我们假设儿子的颜色为直接连向儿子的边的颜色，那么对于两条树链合并时，就要看儿子的颜色是否一样，一样的话就要减去一个贡献。

那也不能暴力枚举啊，所以我们把儿子按颜色排序，暂时记录一下相同颜色儿子的信息。这样发现当前儿子颜色和上一个儿子颜色不同时就把暂时记录的信息和另一组合并。

然后因为还有长度要求啊，是一段区间，所以我们考虑线段树。要区间求最大值。

那么我们开两棵线段树，一棵用来记录颜色相同，一棵用来记录颜色不同的，然后可以启发式一下，按颜色为第一关键字，重量为第二关键字排个序，再线段树合并就行了。

感觉想到点分之后就没那么难了呢。（完全忘了当时的困难）

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 #include <vector>
  5 #define N 100011
  6 #define INF 0x7f7f7f7f
  7 using namespace std;
  8 struct apple{
  9     int v,nxt,q;
 10 }edge[N*4];
 11 int indexx[N],vist[N],dist[N],col[N],n,m,Q[N][2],tot,f[N],sum,siz[N],rt,used[N],ans=INF;
 12 void addedge(int x,int y,int z){
 13     edge[++tot].v=y;
 14     edge[tot].q=z;
 15     edge[tot].nxt=indexx[x];
 16     indexx[x]=tot;
 17 }
 18 void find_rt(int u,int fa){
 19     int t,vv;
 20     t=indexx[u];
 21     f[u]=0;siz[u]=1;
 22     while(t){
 23         vv=edge[t].v;
 24         if(!vist[vv] && vv!=fa){
 25             find_rt(vv,u);
 26             siz[u]+=siz[vv];
 27             f[u]=max(f[u],siz[vv]);
 28         }
 29         t=edge[t].nxt;
 30     }
 31     f[u]=max(f[u],sum-siz[u]);
 32     if(f[u]<f[rt]) rt=u;
 33 }
 34 void dfs(int u,int fa,int c){
 35     if(fa==0) c=0; 
 36     int t,vv;
 37     col[u]=c;
 38     t=indexx[u];
 39     while(t){
 40         vv=edge[t].v;
 41         if(vv!=fa){
 42             dist[vv]=dist[u]+edge[t].q;
 43             if(fa==0) c++;
 44             dfs(vv,u,c);
 45         }
 46         t=edge[t].nxt;
 47     }
 48 }
 49 int solve(int u,int &maxx){
 50     int cnt=0,k=0;
 51     maxx=0;
 52     dist[u]=0;
 53     dfs(u,0,0);
 54     for(int i=1;i<=m;i++){
 55         int x=Q[i][0];
 56         int y=Q[i][1];
 57         used[i]=0;
 58         if(dist[x]+dist[y]>maxx){
 59             maxx=dist[x]+dist[y];
 60             used[i]=++cnt;
 61         }
 62         else if(dist[x]+dist[y]==maxx){
 63             used[i]=cnt;
 64         }
 65     }
 66     for(int i=1;i<=m;i++){
 67         int x=Q[i][0];
 68         int y=Q[i][1];
 69         if(used[i]==cnt){
 70             if(col[x]!=col[y]) return -1;
 71             else if(k && col[x]!=k) return -1;
 72             k=col[x];
 73         }
 74     }
 75     return k;
 76 }
 77 void work(int u){
 78     vist[u]=1;
 79     int maxx=0,t=indexx[u],vv;
 80     int k=solve(u,maxx);
 81     ans=min(ans,maxx);
 82     while(t){
 83         vv=edge[t].v;
 84         if(col[vv]==k && !vist[vv]){
 85             rt=0;sum=siz[vv];
 86             find_rt(vv,u);
 87             work(rt);
 88         }
 89         t=edge[t].nxt;
 90     }
 91 }
 92 int main(){
 93     int x,y,z;
 94     scanf("%d%d",&n,&m);
 95     for(int i=1;i<n;i++){
 96         scanf("%d%d%d",&x,&y,&z);
 97         addedge(x,y,z);
 98         addedge(y,x,z);
 99     }
100     for(int i=1;i<=m;i++){
101         scanf("%d%d",&x,&y);
102         Q[i][0]=x;
103         Q[i][1]=y;
104     }
105     rt=0;f[0]=INF;
106     sum=n;
107     find_rt(1,0);
108     work(rt);
109     printf("%d",ans);
110     return 0;
111 }

树的难题

总结

点分在处理树链的问题还是很强的，但是也不要为了写点分而忘记了树形$dp$。。。不要思维僵化