Max flow P

问题描述:

        有 n 个节点,用 n – 1 条边连接，所有节点都连通了。给出 m 条路径，第 i 条路径为从节点 s_i 到 t_i 。每给出一条路径，路径上所有节点的权值加 1。输出最大权值点的权值。

输入：第 1 行输入 n 和 m。后面 n – 1 行中，每行输入两个整数 x 和 y，表示一条边。后面 m 行中，每行输入两个整数 s 和 t，表示一条路径的起点和终点。

输出：输出一个整数，表示最大权值

数据范围：2 ≤ n ≤ 50000，1 ≤ k ≤ 100000。

输入样例	输出样例
5 10 3 4 1 5 4 2 5 4 5 4 5 4 3 5 4 3 4 3 1 3 3 5 5 4 1 5 3 4	9

树上差分

#include <bits/stdc++.h>
using namespace std;
#define N 50010
struct Edge{int to,next;}edge[2*N];                 //链式前向星
int head[2*N],D[N],deep[N],fa[N][20],ans,cnt;
void init(){                                        //链式前向星：初始化
  for(int i=0;i<2*N;++i){ edge[i].next = -1; head[i] = -1; }
  cnt = 0;
}
void addedge(int u,int v){                          //链式前向星：加边
  edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
}                                                   //以上是链式前向星
void dfs1(int x,int father){                        //求x的深度deep[x]和fa[x][]。father是x的父结点。
  deep[x] = deep[father]+1;                         //深度：比父结点深度多1
  fa[x][0] = father;                                //记录父结点
  for(int i=1; (1<<i) <= deep[x]; i++)              //求fa[][]数组，它最多到根结点
    fa[x][i] = fa[fa[x][i-1]][i-1];
  for(int i=head[x]; ~i; i=edge[i].next)            //遍历结点i的所有孩子。~i可写为i!=-1
    if(edge[i].to != father)                        //邻居：除了父亲，都是孩子
      dfs1(edge[i].to, x);
}
int LCA(int x,int y){
  if(deep[x]<deep[y]) swap(x,y);                    //让x位于更底层，即x的深度值更大
  //（1）把x和y提到相同的深度
  for(int i=19;i>=0;i--)                            //x最多跳19次：2^19 > 500005
    if(deep[x]-(1<<i)>=deep[y])                     //如果x跳过头了就换个小的i重跳
      x = fa[x][i];                                 //如果x还没跳到y的层，就更新x继续跳
  if(x==y) return x;                                //y就是x的祖先
  //（2）x和y同步往上跳，找到LCA
  for(int i=19;i>=0;i--)                            //如果祖先相等，说明跳过头了，换个小的i重跳
    if(fa[x][i]!=fa[y][i]){                         //如果祖先不等，就更新x、y继续跳
      x = fa[x][i]; y = fa[y][i];
  }
  return fa[x][0];                                  //最后x位于LCA的下一层，父结点fa[x][0]就是LCA
}
void dfs2(int u,int fath){
  for (int i=head[u];~i;i=edge[i].next){            //遍历结点i的所有孩子。~i可以写为i!=-1
    int e=edge[i].to;
    if (e==fath) continue;
    dfs2(e,u);
    D[u]+=D[e];
  }
  ans = max(ans,D[u]);                               //最大值
}
int main(){
  init();                                            //链式前向星初始化
  int n,m; scanf("%d%d",&n,&m);
  for (int i=1;i<n;++i){
    int u,v; scanf("%d%d",&u,&v);
    addedge(u,v); addedge(v,u);
  }
  dfs1(1,0);                                         //计算每个结点的深度并预处理fa[][]数组
  for (int i=1; i<=m; ++i){
    int a,b; scanf("%d%d",&a,&b);
    int lca = LCA(a,b);
    D[a]++; D[b]++; D[lca]--; D[fa[lca][0]]--;      //两个线性差分合并成树上差分
  }
  dfs2(1,0);                                        //用差分数组求每个结点的权值
  printf("%d\n",ans);
return 0;
}

笔记：树上差分就是将差分应用在树形数据结构中。u → v分成两个独立的线性差分，一个是u → LCA，区间差分D[u]++，D[F]–，另外一个是v → LCA ，D[v]++，区间差分D[v]++，D[F]–。两个线性差分合并成树上差分，D[a]++; D[b]++; D[lca]–; D[fa[lca][0]]–;