题解 CF191C 【Fools and Roads】

去看题解大佬打的看不懂…只好自己努力（连蒙带抄）写了好久终于过了

竟然没人发树剖？（害我调半天）结合我自己看不懂题解的经验，我尽量写清楚些，顺便介绍几个调错的小技巧hhh

树链剖分的思想？

树剖，简单来说就是将一棵树分成由轻边连成都重链，从而使得问题大大简化

我们假设每一个节点重量是1，那么对于任意一个节点，他的子树中更重的那个，我们称之为重孩子，其他都称之为轻孩子。我们知道，每一个节点都会有一个重孩子，那么这一串重孩子链我们称之为重链，反之呢，连接轻孩子的边称之为轻边

自己随便找些树来画一画，易证每一棵树都可以分为若干条重链，重链与重链间由轻边链接

首先是每个数组的含义

int sz[N],hs[N],f[N],tp[N],dep[N];

• sz是以每个节点为根的子树的重量
• hs是每个节点的重孩子
• f是每个节点的父亲
• tp是每个节点所处的重链的顶
• dep是每个节点在树中的深度

这是树剖的部分

int sz[N],hs[N],f[N],tp[N],dep[N];
void dfs1(int x,int fa){
     dep[x]=dep[fa]+1;
     sz[x]=1;
     f[x]=fa;
     hs[x]=0;
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==fa)   continue;
         dfs1(y,x);
         sz[x]+=sz[y];
         if(sz[y]>sz[hs[x]])
             hs[x]=y;
     }
}
void dfs2(int x,int t){
     tp[x]=t;
     if(hs[x])
         dfs2(hs[x],t);
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==f[x] || y==hs[x]) continue;
         dfs2(y,y);
     }
}

用树剖求LCA的思想是：

• 对于两个点，如果不处于同一条重链，就像上跳出当前重链直到处于同一条，那么此时他们必定一个高一个低

inline int LCA(int x,int y){
     while(tp[x]!=tp[y]){
         if(dep[tp[x]]>=dep[tp[y]])
             x=f[tp[x]];
         else    y=f[tp[y]];         //特别注意，必须跳出重链，也就是跳到顶的父亲上
     }
     return dep[x]>dep[y]?y:x;
}

这道题已经有大佬曰过，差分做法是

++s[x],++s[y],s[LCA(x,y)]-=2;

那么我们在一个dfs中将这个影响施加到整个路径上

int s[N],ans[N],id[N];
void dfs3(int x){
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==f[x]) continue;
         dfs3(y);
         s[x]+=s[y];
     }
     ans[id[x]]=s[x];
 }

感觉这个做法还不错，最慢也不过300ms

完整内容贴上

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int N=210000,M=N<<1;//请注意2倍...
struct node{
     int x,y;
     node(int x=0,int y=0):x(x),y(y){}
}; node edge[N];//单项不开二倍
int G[M],head[N],nxt[M],e_cnt=0;
inline void add(int x,int y){
     //前向星
      G[++e_cnt]=y;
     nxt[e_cnt]=head[x];head[x]=e_cnt;
 }
int sz[N],hs[N],f[N],tp[N],dep[N]; //我猜你们记不住数组的含义，往前翻翻吧
void dfs1(int x,int fa){
     dep[x]=dep[fa]+1;
     sz[x]=1;
     f[x]=fa;
     hs[x]=0;
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==fa)   continue;
         dfs1(y,x);
         sz[x]+=sz[y];
         if(sz[y]>sz[hs[x]])
             hs[x]=y;
     }
}
void dfs2(int x,int t){
     tp[x]=t;
     if(hs[x])
         dfs2(hs[x],t);
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==f[x] || y==hs[x]) continue;
         dfs2(y,y);
     }
}
inline int LCA(int x,int y){
     while(tp[x]!=tp[y]){
         if(dep[tp[x]]>=dep[tp[y]])
             x=f[tp[x]];
         else    y=f[tp[y]];
     }
     return dep[x]>dep[y]?y:x;
 }
int s[N],ans[N],id[N];
void dfs3(int x){
     for(int i=head[x];i;i=nxt[i]){
         int y=G[i];
         if(y==f[x]) continue;
         dfs3(y);
         s[x]+=s[y];
    }
    ans[id[x]]=s[x];
 }
int main(){
     ios::sync_with_stdio(0);     //关闭同步
     int n,k;//n个点和k次问询
     cin>>n;
     for(int i=1;i<n;++i){
         int x,y;
         cin>>x>>y;
         edge[i]=node(x,y);
         add(x,y);   add(y,x);
     }
     dfs1(1,0);
     dfs2(1,1);
     //这个题要按照边的顺序输出，很烦
     //我们将边的权值施加到深度较大的那个点上
      for(int i=1;i<n;++i)
         if(dep[edge[i].x]>dep[edge[i].y])
           id[edge[i].x]=i;
         else
           id[edge[i].y]=i;
     cin>>k;
     for(int i=1;i<=k;++i){
         int x,y;
         cin>>x>>y;
         ++s[x],++s[y],s[LCA(x,y)]-=2;
         //cout<<"lca="<<LCA(x,y)<<endl;
         //这里是个debug的好地方，对于本题来说差分难度不大，而lca直接是模板       //在这里检查lca结果可以迅速确定出错位置
      }
     dfs3(1);//处理权值，差分
     for(int i=1;i<n;++i)
         //输答案跑路
          cout<<ans[i]<<' ';
      return 0;
}