Max Flow

题意：
有一颗n个节点的树，有k次操作，每次操作给出二个节点，然后将二个节点及二个节点之间的节点权值都加一，然后求最后树中权值最大的节点的权值为多少？

思路：
lca+差分：
用lca求出二个节点u、v的最近公共祖先k，k的父亲节点为kp；
要使u、v路经上节点权值加一则val[u]、val[v]进行加一，表示经过u、v节点时值加一，然后k位置此时相当与加了二，所以val[k]要减一，最后val[kp]减一表示经过kp节点时值减一。
求点的权值时从叶子节点开始向根节点计算,取最大值当结果即可。

代码：

#include<bits/stdc++.h>

#define ll long long
#define eps 1e-8

using namespace std;

const ll inf=1e9+7;

int val[100005], dep[100005], parent[21][100005], qi=0, ma=0;

vector<int> g[100005];

void dfs(int v,int f,int k)
{
    dep[v]=k;
    parent[0][v]=f;
    for(int i=0; i<g[v].size(); i++)
    {
        int u=g[v][i];
        if(u==f)
        {
            continue;
        }
        dfs(u,v,k+1);
    }
}

int dfs1(int v,int f)
{
    int z=val[v];
    for(int i=0; i<g[v].size(); i++)
    {
        int u=g[v][i];
        if(u==f)
        {
            continue;
        }
        z=z+dfs1(u,v);
    }
    ma=max(ma,z);
    return z;
}

int quitv(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    int k=dep[u]-dep[v];
    for(int i=18; i>=0; i--)
    {
        if((k>>i)&1)
        {
            u=parent[i][u];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=18; i>=0; i--)
    {
        if(parent[i][u]!=parent[i][v])
        {
            u=parent[i][u];
            v=parent[i][v];
        }
    }
    return parent[0][u];
}

int main()
{
    int n, q;
    scanf("%d%d",&n,&q);
    for(int i=1; i<n; i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1, 1);
    for(int k=1; k<=18; k++)
    {
        for(int i=1; i<=n; i++)
        {
            if(parent[k-1][i]==-1)
            {
                parent[k][i]=-1;
            }
            else
            {
                parent[k][i]=parent[k-1][parent[k-1][i]];
            }
        }
    }
    while(q--)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        int k=quitv(u,v);
        val[k]--;
        if(parent[0][k]!=-1)
            val[parent[0][k]]--;
        val[u]++;
        val[v]++;
    }
    dfs1(1,-1);
    cout << ma << endl;
    return 0;
}