LCA及应用

定义：

  最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

性质：

1. $LCA\left(u\right)=u$LCA(u)=u;
2. $u$u是 $v$v的祖先，当且仅当 $LCA(u,v)=u$LCA(u,v)=u；
3. 如果 $u$u不为 $v$v的祖先并且 $v$v不为 $u$u的祖先，那么 $u,v$u,v分别处于 $LCA(u,v)$LCA(u,v)的两棵不同子树中；
4. 前序遍历中, $LCA\left(S\right)$LCA(S) 出现在所有 $S$S 中元素之前，后序遍历中 $LCA\left(S\right)$LCA(S) 则出现在所有 $S$S 中元素之后；
5. 两点的最近公共祖先必定处在树上两点间的最短路上；
6. $d(u,v)=h\left(u\right)+h\left(v\right)-2h\left(LCA\right(u,v\left)\right)$d(u,v)=h(u)+h(v)−2h(LCA(u,v)),其中 $d$d 是树上两点间的距离， $h$h 代表某点到树根的距离。

算法实现：

  存图时存双向边，可以任选一点为根。

1.朴素算法：

  让 $u$u 和 $v$v 中深度深的点先走 $\mid depth\left[v\right]-depth\left[u\right]\mid$∣depth[v]−depth[u]∣ 步，然后两个点同时向上走，直到走到同一个节点。

复杂度：

$O\left(n\right)$O(n)

2.倍增（基于二分搜索，在线）：

  朴素算法的改进算法。
  通过预处理 $pre\left[k\right]\left[i\right]$pre[k][i] 数组，游标可以快速移动，大幅减少了游标跳转次数。 $pre\left[k\right]\left[i\right]$pre[k][i] 表示点 $i$i 的第 $2^k$2k 个祖先。 $pre\left[k\right]\left[i\right]$pre[k][i] 数组可以通过 $dfs$dfs 预处理出来。

复杂度：

每次询问的复杂度为 $O\left(logn\right)$O(logn)，预处理 $pre\left[k\right]\left[i\right]$pre[k][i] 数组的复杂度为 $O\left(nlogn\right)$O(nlogn)。

主要优化：

$\left(1\right).$(1).对于深度不同的两个点 $u$u 和 $v$v ，其深度的差值为 $d=\mid depth\left[u\right]-depth\left[v\right]\mid$d=∣depth[u]−depth[v]∣ ,然后对其进行二进制拆分，借助 $pre\left[k\right]\left[i\right]$pre[k][i] 数组，将差值消除，使得两个点的深度相同。
$\left(2\right).$(2).将两个点调整至相同位置之后，与朴素算法相同，两个点同时向上跳。具体实现：从最大可能的 $k$k 值开始尝试，直到 $0$0 (包括 $0$0 )。如果 $pre\left[k\right]\left[u\right]!=pre\left[k\right]\left[v\right]$pre[k][u]!=pre[k][v] ,那么 $u=pre\left[k\right]\left[u\right],v=pre\left[k\right]\left[v\right]$u=pre[k][u],v=pre[k][v] 。否则继续尝试。
注意不能从低位到高位继续尝试，会把 $lca$lca 跳过。
该技巧在 $LCA$LCA 以外的地方也可使用。

具体代码实现：

const int N=1e4+5;
const int maxk=20;//最大可能k值
vector<int>pic[N];//存图
int depth[N],pre[maxk][N];//点的深度，及预处理的2^k表
int root,n;//根节点，节点数
void dfs(int v,int p,int d)//(当前点，其父亲节点，其深度)
{//处理出各点的深度和父亲
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        if(pic[v][i]!=p)
            dfs(pic[v][i],v,d+1);
    }
}
void init()
{
    //预处理出depth和pre[0][i];
    dfs(root,-1,0);//根节点父亲=-1
    //预处理出全部的pre
    for(int k=0;k+1<maxk;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])//保持u的深度小于v
        swap(u,v);
    //消除深度差
    for(int k=0;k<maxk;k++)//枚举差值的二进制位,从低到高，从高到低均可
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];//深度差-=2^k
    }
    if(u==v)
        return u;
    //二分搜索计算lca
    for(int k=maxk-1;k>=0;k--)//只能从高到低，从低到高会把lca跳过
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}

例题：
1.Nearest Common Ancestors POJ - 1330【模板题】

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e4+5;
vector<int>pic[N];//存图
int depth[N],pre[20][N],degree[N];//点的深度，及预处理的2^k表
int root,maxk=20,n;//根节点，最大可能k值，节点数
void dfs(int v,int p,int d)//处理出各点的深度和父亲
{
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        if(pic[v][i]!=p)
            dfs(pic[v][i],v,d+1);
    }
}
void init()
{
    //预处理出depth和pre[0][i];
    dfs(root,-1,0);
    //预处理出全部的pre
    for(int k=0;k+1<maxk;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])//保持u的深度小于v
        swap(u,v);
    //消除深度差
    for(int k=0;k<maxk;k++)//枚举差值的二进制位,从低到高，从高到低均可
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];//深度差-=2^k
    }
    if(u==v)
        return u;
    //二分搜索计算lca
    for(int k=maxk-1;k>=0;k--)//只能从高到低，从低到高会把lca跳过
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int u,v;
        memset(degree,0,sizeof(degree));
        for(int i=1;i<=n;i++)
            pic[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            pic[u].push_back(v);
            degree[v]++;
        }
        scanf("%d%d",&u,&v);
        for(int i=1;i<=n;i++)
        {
            if(degree[i]==0)
            {
                root=i;
                break;
            }
        }
        init();
        printf("%d\n",lca(u,v));
    }
    return 0;
}

2.How far away ？ HDU - 2586 【树上两点间最短路】
  在 $dfs$dfs 时预处理每点到根的距离，套倍增求出 $lca$lca 后，由性质6，求出两点间距离。

#include <bits/stdc++.h>
using namespace std;
const int N=4e4+5;
const int maxk=20;
typedef pair<int,int> P;
int root,n;
int depth[N],degree[N],dis[N],pre[maxk][N];
vector<P>pic[N];
void dfs(int v,int p,int d)
{
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        P t=pic[v][i];
        if(p!=t.second)
        {
            dis[t.second]=dis[v]+t.first;
            dfs(t.second,v,d+1);
        }
    }
}
void init()
{
    dfs(root,-1,0);
    for(int k=0;k+1<maxk;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])
        swap(u,v);
    for(int k=0;k<maxk;k++)
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];
    }
    if(u==v)
        return u;
    for(int k=maxk-1;k>=0;k--)
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}
int main()
{
    int t,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(degree,0,sizeof(degree));
        memset(dis,0,sizeof(dis));
        for(int i=1;i<=n;i++)
            pic[i].clear();
        int u,v,w;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            pic[u].push_back(make_pair(w,v));
            degree[v]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(degree[i]==0)
            {
                root=i;
                break;
            }
        }
        init();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            int ans=lca(u,v);
            printf("%d\n",dis[u]+dis[v]-2*dis[ans]);
        }
    }
    return 0;
}

3.Tarjan算法（离线）：

  在一次遍历中把所有询问一次性解决，其时间复杂度是 $O(n+q)$O(n+q)。
  算法的思想比倍增要简单，主要是   $dfs$dfs+并查集。代码量较短，相对稳定。在一些题目中会出现mle.
  对于每一个点，当该点没有孩子节点或孩子节点已全部访问完，开始看其关系节点。
伪代码：

Tarjan(u)//marge和find为并查集合并函数和查找函数
{
    for each(u,v)    //访问所有u子节点v
    {
        Tarjan(v);        //继续往下遍历
        marge(u,v);    //合并v到u上
    }
    标记v被访问过;
    for each(u,e)    //访问所有和u有询问关系的e
    {
        如果e被访问过;
        u,e的最近公共祖先为find(e);
    }
}

过程请点击此处
3.Distance Queries POJ - 1986【模板】
用链式前向星来代替vector会快很多。

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
using namespace std;
const int N=4e4+5;
typedef pair<int,int> P;
vector<P>pic[N],link[N];
int dis[N],pre[N],ans[N];
bool vis[N];
int n;
int Find(int x)
{
    if(x!=pre[x])
        return pre[x]=Find(pre[x]);
    else
        return x;
}
void Join(int x,int y)
{
    int px=Find(x),py=Find(y);
    if(px!=py)
        pre[px]=py;
}
void tarjan(int v,int p)
{
    for(int i=0;i<pic[v].size();i++)
    {
        P t=pic[v][i];
        if(!vis[t.second]&&t.second!=p)//因为存的是双向边，否则再次访问父亲
        {
            dis[t.second]=dis[v]+t.first;
            tarjan(t.second,v);
            Join(t.second,v);
        }
    }
    vis[v]=1;//不能放在上面循环中，可能询问两个相同的点
    for(int i=0;i<link[v].size();i++)
    {
        P t=link[v][i];
        if(vis[t.first])
        {
            int fa=Find(t.first);
            ans[t.second]=dis[v]+dis[t.first]-2*dis[fa];//对应存入答案
        }
    }
}
int main()
{
    int m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        char s[8];
        int u,v,w,k;
        for(int i=0;i<=n;i++)
        {
            pic[i].clear();
            link[i].clear();
            pre[i]=i;
        }
        memset(vis,0,sizeof(vis));
        memset(dis,0,sizeof(dis));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%s",&u,&v,&w,s);
            pic[u].push_back(make_pair(w,v));
            pic[v].push_back(make_pair(w,u));
        }
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&u,&v);
            link[u].push_back(make_pair(v,i));//给询问编号
            link[v].push_back(make_pair(u,i));
        }
        tarjan(1,1);//任选一点为根
        for(int i=1;i<=k;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

4.基于RMQ（ $dfs$dfs序+ST表）:

将LCA问题转化成RMQ问题。

树的 $DFS$DFS序:

  简单来讲就是对树从根开始进行深搜，按搜到的时间顺序把所有节点打上时间戳。用一个数组 $vs\left[\right]$vs[]来专门存放 $dfs$dfs树得到的点，共 $2\ast n-1$2∗n−1 个。其中有些点可能出现多次，有些点可能出现一次。

过程见代码:

void dfs(int v,int p,int d,int &cnt)//当前点，父亲节点，深度，vs数组中的位置
{//cout<<"cnt="<<cnt<<endl;
    id[v]=cnt;
    vs[cnt]=v;
    depth[cnt++]=d;
    for(int i=0;i<pic[v].size();i++)
    {
        P t=pic[v][i];
        if(t.second!=p)
        {
            dis[t.second]=dis[v]+t.first;//有边权时
            dfs(t.second,v,d+1,cnt);
            vs[cnt]=v;
            depth[cnt++]=d;
        }
    }
}

  同时，和倍增类似，需要纪律下每个点的深度 $depth\left[i\right]$depth[i] 数组。此外，还有数组 $id\left[i\right]$id[i],记每个点第一次在vs数组中出现的位置。
以上为预处理中 $dfs$dfs的过程。
  接下来，用常用的 $ST$ST表法解决 $RMQ$RMQ问题。

$ST$ST表：

  ST 表基于倍增思想，可以做到 $O\left(nlogn\right)$O(nlogn) 预处理， $O\left(1\right)$O(1) 回答每个询问。但是不支持修改操作。
  基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$2i 步的话，询问时的复杂度仍旧是 $O\left(logn\right)$O(logn)。
我们发现 $max(x,x)=x$max(x,x)=x ，也就是说，区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,已达到 $O\left(1\right)$O(1) 的询问。

具体实现：

预处理部分：
$f\left[i\right]\left[j\right]$f[i][j] 表示区间 $[i,i+2^j-1]$[i,i+2j−1]内的最值。
显然， $f\left[i\right]\left[0\right]=a_i$f[i][0]=ai​；
根据定义式，第二维就相当于倍增的时候“跳了 $2^j-1$2j−1 步”，依据倍增的思路，写出状态转移方程：
f[i][j]=max(f[i][j−1],f[i+(1<<(j−1))][j−1])
相当于把区间 $[i,i+2^j-1]$[i,i+2j−1]划分为两个部分 $[i,i+2^{(j-1)}-1]和[i+2^{(j-1)},i+2^j-1]$[i,i+2(j−1)−1]和[i+2(j−1),i+2j−1],注意第二维是 $j-1$j−1 ,其相当于一个长度差值，起点不同，离终点的差值也不同。
如图：

实现代码：

void st(int n)//取2*n-1，因为从0开始
{
    //int cnt=0;
    //dfs(0,-1,0,cnt);
    int mak=(int)(log2(1.0*n));//第二维的最大值
    for(int i=0;i<=n;i++)
        f[i][0]=i;
    for(int k=1;k<=mak;k++)
    {
        for(int i=0;i+(1<<k)-1<=n;i++)
        {
            int a=f[i][k-1];
            int b=f[i+(1<<(k-1))][k-1];//不能把k-1写成了k,一定要注意f数组的含义
            if(depth[a]>depth[b])//此处为具体问题
                f[i][k]=b;
            else
                f[i][k]=a;
        }
    }
}

查询：
对于查询区间[l,r]而言，可以将其划分为两部分。
$[l,l+2^k-1]和[r-2^k+1,r]$[l,l+2k−1]和[r−2k+1,r]，其中 $k=log2(r-l+1)$k=log2(r−l+1)；
从而用两个区间将目标区间覆盖掉。
例题：
Design the city ZOJ - 3195：
  求三个点之间的最短距离，任意两个点求出 $lca$lca 后求出任意两个点之间的最短距离，求和，然后除2。
因为把 $k-1$k−1写成了 $k$k, $debug$debug好久。😭

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
const int N=5e4+5;
typedef pair<int,int> P;
int id[N],vs[N<<1],depth[N<<1],dis[N];//开2倍
//id:表示点i在vs中第一次出现的位置;vs:表示dfs生成的dfs序表;depth:表示vs数组中每个位置所表示的点的深度;dis:每个点离根的距离
int f[N<<1][20];//st表
vector<P>pic[N];//存图
void dfs(int v,int p,int d,int &cnt)//当前点，父亲节点，深度，vs数组中的位置
{//cout<<"cnt="<<cnt<<endl;
    id[v]=cnt;
    vs[cnt]=v;
    depth[cnt++]=d;
    for(int i=0;i<pic[v].size();i++)
    {
        P t=pic[v][i];
        if(t.second!=p)//存双向边，否则找到父亲
        {
            dis[t.second]=dis[v]+t.first;
            dfs(t.second,v,d+1,cnt);
            vs[cnt]=v;
            depth[cnt++]=d;
        }
    }
}
void st(int n)//取2*n-1，因为从0开始
{
    int cnt=0;
    dfs(0,-1,0,cnt);//任取一点为父亲
    int mak=(int)(log2(1.0*n));
    for(int i=0;i<=n;i++)
        f[i][0]=i;
    for(int k=1;k<=mak;k++)
    {
        for(int i=0;i+(1<<k)-1<=n;i++)
        {
            int a=f[i][k-1];
            int b=f[i+(1<<(k-1))][k-1];//把k-1写成了k,一定要注意f数组的含义
            if(depth[a]>depth[b])
                f[i][k]=b;
            else
                f[i][k]=a;
        }
    }
}
int rmq(int l,int r)
{
    int k=(int)(log2(1.0*r-l+1));
    int a=f[l][k];
    int b=f[r-(1<<k)+1][k];
    if(depth[a]<depth[b])
        return a;
    else
        return b;
}
int lca(int u,int v)
{
    int l=id[u];
    int r=id[v];
    if(l>r)
        swap(l,r);
    return vs[rmq(l,r)];
}
int main()
{
    int n,cot=0;
    while(scanf("%d",&n)!=EOF)
    {
        if(cot++>0)
            cout<<endl;
        int u,v,w,q;
        for(int i=0;i<=n;i++)
            pic[i].clear();
        memset(dis,0,sizeof(dis));
        memset(f,0,sizeof(f));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            pic[u].push_back(make_pair(w,v));
            pic[v].push_back(make_pair(w,u));
        }
        st(n*2-1);
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            int x=lca(u,v);
            int y=lca(u,w);
            int z=lca(v,w);//cout<<"x="<<x<<" y="<<y<<" z="<<z<<endl;
            int ans=dis[u]+dis[v]+dis[w]-dis[x]-dis[y]-dis[z];
            printf("%d\n",ans);
        }
    }
    return 0;
}

练习题
Connections between cities HDU - 2874
  树变成了森林，首先可以利用并查集处理出每个树的根，然后把所有树的根连接到一个虚点0上，并赋权值0。然后对于每次输入的两个点，判断是否在同一棵树上，再求lca。
  一开始想用入度为0的点作根，但因为存单向边，所以一棵树上入度为0的点可能有多个。所以不行。

#include <bits/stdc++.h>//引入0为根节点，把森林转化为树，用并查集来找每个树的根
using namespace std;
const int N=1e4+5;
const int mak=25;
typedef long long ll;
typedef pair<ll,int>P;
int pre[mak][N],depth[N],father[N];
ll dis[N];
bool vis[N];
vector<P>pic[N];
int n;
int Find(int x)
{
    if(x!=father[x])
        return father[x]=Find(father[x]);
    return x;
}
void Join(int x,int y)
{
    int px=Find(x),py=Find(y);
    if(px!=py)
        father[px]=py;
}
void dfs(int v,int p,int d)
{
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        P t=pic[v][i];
        if(p!=t.second)
        {
            dis[t.second]=dis[v]+t.first;
            dfs(t.second,v,d+1);
        }
    }
}
void init()
{
    dfs(0,-1,0);
    for(int k=0;k+1<mak;k++)
    {
        for(int i=0;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])
        swap(u,v);
    for(int k=0;k<mak;k++)
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];
    }
    if(u==v)
        return u;
    for(int k=mak-1;k>=0;k--)
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}
int main()
{
    int m,c;
    while(scanf("%d%d%d",&n,&m,&c)!=EOF)
    {
        int u,v;
        ll w;
        memset(vis,0,sizeof(vis));
        dis[0]=0;
        for(int i=0;i<=n;i++)
        {
            pic[i].clear();
            father[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&u,&v,&w);
            Join(u,v);
            pic[u].push_back(make_pair(w,v));
            pic[v].push_back(make_pair(w,u));
        }
        for(int i=1;i<=n;i++)
        {
            int t=Find(i);
            if(!vis[t])
            {
                pic[0].push_back(make_pair(0,t));
                pic[t].push_back(make_pair(0,0));
                vis[t]=1;
            }
        }
        init();
        for(int i=1;i<=c;i++)
        {
            scanf("%d%d",&u,&v);
            if(Find(u)==Find(v))
            {
                int ans=lca(u,v);
                printf("%lld\n",dis[u]+dis[v]-2*dis[ans]);
            }
            else
                printf("Not connected\n");
        }
    }
    return 0;
}

Network HDU - 3078
涉及到单点修改和区间第k大的询问。
本来以为要把树拍平，然后用树状数组。结果直接暴力，把路径上所有点排序输出即可。

#include <bits/stdc++.h>
using namespace std;
const int N=8e4+5;
const int mak=20;
int latency[N];
vector<int>pic[N],laten;
int pre[mak][N],depth[N];
int n;
void dfs(int v,int p,int d)
{
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        if(p!=pic[v][i])
            dfs(pic[v][i],v,d+1);
    }
}
void init()
{
    dfs(1,-1,0);
    for(int k=0;k+1<mak;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])
        swap(u,v);
    for(int k=0;k<mak;k++)
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];
    }
    if(u==v)
        return u;
    for(int k=mak-1;k>=0;k--)
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}
bool cmp(int x,int y)
{
    return x>y;
}
int solve(int fa,int u,int v,int k)
{
    laten.clear();
    laten.push_back(latency[u]);
    if(u!=v)
        laten.push_back(latency[v]);
    if(u!=fa&&v!=fa)
        laten.push_back(latency[fa]);
    while(pre[0][u]!=fa&&u!=fa)
    {
        laten.push_back(latency[pre[0][u]]);
        u=pre[0][u];
    }
    while(pre[0][v]!=fa&&v!=fa)
    {
        laten.push_back(latency[pre[0][v]]);
        v=pre[0][v];
    }
    if(laten.size()<k)
        return -1;
    sort(laten.begin(),laten.end(),cmp);
    return laten[k-1];
}
int main()
{
    int q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        int k,u,v;
        for(int i=1;i<=n;i++)
            scanf("%d",&latency[i]);
        for(int i=1;i<=n;i++)
            pic[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            pic[u].push_back(v);
            pic[v].push_back(u);
        }
        init();
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d",&k,&u,&v);
            if(k==0)
                latency[u]=v;
            else
            {
                //printf("%d\n",lca(u,v));
                int ans=solve(lca(u,v),u,v,k);
                if(ans==-1)
                    printf("invalid request!\n");
                else
                    printf("%d\n",ans);
            }
        }
    }
    return 0;
}

Housewife Wind POJ - 2763【lca+BIT维护边权修改】
  对于边权的修改，只要普通的rmq是无法处理的，因此可以借助树状数组来维护。
  首先，利用dfs序把树型图转化为连续数组存储，和基于rmq的lca算法操作相同。同时在dfs时，把边权变为点权，存入树状数组中维护。因为，节点u和v之间的路径，就是dfs得到的序列中u和v之间所有的边减去往返重复的部分得到的结果。所以，只要令边的权值向叶子方向为正，向根方向为负，这样往返的部分就可以抵消了。
  但是，此时还是要借助两个点lca来求两点之间的最短距离，不能直接通过树状数组求个差。（找了好久的bug）
  总的思路就是： $lca+bit$lca+bit 求两点间距离， $bit$bit 维护边权的修改。
poj恶心的是卡vector。

#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+5;
typedef long long ll;
struct edg
{
    int to;
    ll w;
    int num;//边的序号
    int next;
}edge[N<<1];
int head[N];
int vs[N<<1],id[N],e[N<<1],depth[N<<1],f[N<<1][25];
ll bit[N<<1];
int n,cot;
void init()
{
    memset(head,-1,sizeof(head));
    cot=1;
}
void edgeadd(int from,int to,int ww,int ii)
{
    edge[cot].to=to;
    edge[cot].w=ww;
    edge[cot].num=ii;
    edge[cot].next=head[from] ;
    head[from]=cot++ ;
}
void update(int x,ll nm)
{
    while(x<=2*n)
    {
        bit[x]+=nm;
        x+=x&(-x);
    }
}
ll query(int x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=bit[x];
        x-=x&(-x);
    }
    return sum;
}
void dfs(int v,int p,int d,int &cnt)
{
    id[v]=cnt;
    depth[cnt]=d;
    vs[cnt++]=v;
    for(int i=head[v];i!=-1;i=edge[i].next)
    {
        edg t=edge[i];
        if(t.to!=p)
        {
            e[2*t.num]=cnt;//正边对应编号
            update(cnt,t.w);//在dfs的同时进行bit数组的初始化
            dfs(t.to,v,d+1,cnt);
            e[2*t.num-1]=cnt;//反边对应编号
            update(cnt,-t.w);
            depth[cnt]=d;
            vs[cnt++]=v;
        }
    }
}
void st()
{
    int mak=(int)log2(2.0*n-1);
    for(int i=0;i<2*n;i++)
        f[i][0]=i;
    for(int k=1;k<=mak;k++)
    {
        for(int i=1;i+(1<<k)-1<=2*n-1;i++)
        {
            int a=f[i][k-1];
            int b=f[i+(1<<(k-1))][k-1];
            if(depth[a]<depth[b])
                f[i][k]=a;
            else
                f[i][k]=b;
        }
    }
}
int rmq(int l,int r)
{
    int k=(int)log2(1.0*r-l+1);
    int a=f[l][k];
    int b=f[r-(1<<k)+1][k];//犯傻：把 k写成了 r
    if(depth[a]<depth[b])
        return a;
    else
        return b;
}
int lca(int u,int v)
{
    int l=id[u];
    int r=id[v];
    if(l>r)
        swap(l,r);
    return vs[rmq(l,r)];
}
int main()
{
    int q,s;
    while(scanf("%d%d%d",&n,&q,&s)!=EOF)
    {
        int u,v;
        ll w;
        init();
        memset(bit,0,sizeof(bit));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%lld",&u,&v,&w);
            edgeadd(u,v,w,i);
            edgeadd(v,u,w,i);
        }
        int cnt=1;
        dfs(1,-1,0,cnt);
        st();
        for(int i=1;i<=q;i++)
        {
            scanf("%d",&v);
            if(v==0)
            {
                scanf("%d",&u);
                int t=lca(s,u);
                printf("%lld\n",query(id[s])+query(id[u])-2*query(id[t]));
                s=u;
            }
            else
            {
                scanf("%d%lld",&u,&w);
                ll t=query(e[u*2])-query(e[u*2]-1);
                update(e[u*2],w-t);
                update(e[u*2-1],t-w);
            }
        }
    }
    return 0;
}
/* 6 6 1 1 2 2 1 4 1 1 5 2 2 3 1 2 6 1 0 6 0 5 */

CodeForce 1304E 1-Trees and Queries