洛谷P3128 [USACO15DEC]Max Flow P/树上差分模板

原题链接

题意:

给定一棵n个点的树，n-1条无向边，有k次询问，每次给两个点x、y，将这两个点的最短路径经过的每个点+1（包括x，y），求经过次数最多的那个点经过了多少次。

数据范围：

\(2≤n≤50,000\)
\(1≤k≤100,000\)

思路：

一看这数据就不能用暴力了，肯定得用差分。
很明显这就是点的差分模板题啊！
把x，y两个点前缀和数组+1，把\(LCA(x,y)\)以及\(LCA(x,y)\)的父亲节点-1，
好了，这就结束了。

code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N=100005;
const int M=25;
int cnt,head[N],fa[N][M],total[N],n,m,dep[N],b[N];
struct node{
    int u,v,w,next;
}ed[N];
void add_edge(int u,int v)
{
    cnt++;
    ed[cnt].u=u;
    ed[cnt].v=v;
    ed[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int xx)//本次DFS是求出倍增数组dou[][]
{
    for(int i=1;i<=20;i++)
    {
        fa[xx][i]=fa[fa[xx][i-1]][i-1];
    }
    for(int i=head[xx];i;i=ed[i].next)
    {
        int temp=ed[i].v;
        if(!b[temp])
        {
            b[temp]=1;
            dep[temp]=dep[xx]+1;
            dou[temp][0]=xx;
            dfs(temp);
        }
    }
} 
int LCA(int x,int y)
{
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    int temp=dep[x]-dep[y];
    for(int i=20;i>=0;i--)
    {
        if((1<<i)&temp)
        {
            x=fa[x][i];
        }
    }
    if(x==y)
    return x;
    for(int i=20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
void dfs2(int xx)//本次DFS求出前缀和数组
{
    for(int i=head[xx];i;i=ed[i].next)
    {
        int temp=ed[i].v;
        if(!b[temp])
        {
            b[temp]=1;
            dfs2(temp);
            total[xx]+=total[temp];
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x);
    }
    b[1]=1;
    dep[1]=1;
    dfs(1);
    memset(b,0,sizeof b);
    while(m--)
    {
        int xx,yy;
        cin>>xx>>yy;
        int lca=LCA(xx,yy); 
        total[xx]++;
        total[yy]++;
        total[lca]--;
        total[fa[lca][0]]--;
    }
    b[1]=1;
    dfs2(1);
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,total[i]);
    }
    cout<<maxn;
    return 0;
}

洛谷P3128 [USACO15DEC]Max Flow P/树上差分模板

原文：https://www.cnblogs.com/pjxpjx/p/12441261.html