UESTC-92: Journey（LCA 倍增 | 树剖）

LCA 树链剖分

Description

Bob has traveled to byteland, he find the N cities in byteland formed a tree structure, a tree structure is very special structure, there is exactly one path connecting each pair of nodes, and a tree with N nodes has N−1 edges.
As a traveler, Bob wants to journey between those N cities, and he know the time each road will cost.
He advises the king of byteland building a new road to save time, and then, a new road was built.
Now Bob has Q journey plan, give you the start city and destination city, please tell Bob how many time is saved by add a road if he always choose the shortest path. Note that if it's better not journey from the new roads, the answer is 0.

Input

First line of the input is a single integer $T(1≤T≤20)$, indicating there are T test cases.

For each test case, the first will line contain two integers $N(2≤N≤10^5)$ and $Q(1≤Q≤10^5)$, indicating the number of cities in byteland and the journey plans. Then N line followed, each line will contain three integer $x$, $y(1≤x,y≤N)$ and $z(1≤z≤1000)$ indicating there is a road cost z time connect the $x_{th}$ city and the $y_{th}$ city, the first $N−1$ roads will form a tree structure, indicating the original roads, and the $N_{th}$ line is the road built after Bob advised the king.
Then $Q$ line followed, each line will contain two integer $x$ and $y(1≤x,y≤N)$, indicating there is a journey plan from the $x_{th}$ city to $y_{th}$ city.

Output

For each case, you should first output Case #t: in a single line, where t indicating the case number between 1 and T, then Q lines followed, the $i_{th}$ line contains one integer indicating the time could saved in $i_{th}$ journey plan.

Sample Input

1 
5 5 
1 2 3 
2 3 4 
4 1 5 
3 5 1 
3 1 5 
1 2 
1 3 
2 5 
3 4 
4 5

Sample Output

Case #1:
0 
2 
0 
2 
2

题意： t组数据，有n个点，q次询问，1到n-1行表示最初x到y点距离为z，第n行为新加入的一条边a到b距离为c，每次询问：新加入边之后节省了多少路程，若没有则输出0。

分析：原图两点之间的距离可以用LCA求得，dis[x,y]=dis[x]+dis[y]-2*dis[LCA(x,y)]；若要经过新加入的边(a,b,c)，起点x，终点y，那么一定有：从x→a，a→b，b→y或者x→b，b→a，a→y；ab间距离为c，其他两段距离用LCA求得。最后与原路程比较即可。

倍增

• 代码：

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
const int maxn=1e5+5;
using namespace std;
int n,q;
int dep[maxn],dis[maxn];
int fa[maxn][15];
struct node
{
    int en,val;
    node(int enn=0,int vall=0)
    {
        en=enn;
        val=vall;
    }
};
vector<node> V[maxn];
void clr()
{
    memset(dep,0,sizeof(dep));
    memset(dis,0,sizeof(dis));
    memset(fa,0,sizeof(fa));
    for(int i=0;i<=n;i++)
        V[i].clear();
}
void dfs(int u,int f,int d)
{
    fa[u][0]=f;
    for(int i=1;i<15;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    dep[u]=d;
    for(int i=0;i<V[u].size();i++)
    {
        node v=V[u][i];
        if(v.en==f) continue;
        dis[v.en]=dis[u]+v.val;
        dfs(v.en,u,d+1);
    }
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    for(int i=0;i<15;i++)
        if((dep[v]-dep[u])>>i&1)
        v=fa[v][i];
    if(u==v) return u;
    for(int i=14;i>=0;i--)
    {
        if(fa[u][i]!=fa[v][i])
        {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int main()
{
    int t,o=0;
    int x,y,z;
    int a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        clr();
        scanf("%d%d",&n,&q);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            V[x].push_back(node(y,z));
            V[y].push_back(node(x,z));
        }
        dfs(1,0,1);
        scanf("%d%d%d",&a,&b,&c);
        printf("Case #%d:\n",++o);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            int d1=dis[x]+dis[y]-2*dis[LCA(x,y)];
            int d2=dis[x]+dis[a]-2*dis[LCA(x,a)]+dis[y]+dis[b]-2*dis[LCA(y,b)]+c;
            int d3=dis[x]+dis[b]-2*dis[LCA(x,b)]+dis[y]+dis[a]-2*dis[LCA(y,a)]+c;
            d2=min(d2,d3);
            printf("%d\n",d1-d2<0?0:d1-d2);
        }
    }
    return 0;
}

树剖求LCA

• 代码：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,q;
int dis[maxn];
int siz[maxn],dep[maxn],fa[maxn],son[maxn];
int top[maxn];
struct node
{
    int en,val;
    node(int enn=0,int vall=0)
    {
        en=enn;
        val=vall;
    }
};
vector<node> V[maxn];
void clr()
{
    memset(dis,0,sizeof(dis));
    memset(dep,0,sizeof(dep));
    memset(fa,0,sizeof(fa));
    memset(son,0,sizeof(son));
    for(int i=0;i<=n;i++)
        V[i].clear();
}
void dfs1(int u,int f,int d)
{
    dep[u]=d;
    fa[u]=f;
    siz[u]=1;
    for(int i=0;i<V[u].size();i++)
    {
        node v=V[u][i];
        if(v.en==f) continue;
        dis[v.en]=dis[u]+v.val;
        dfs1(v.en,u,d+1);
        if(siz[v.en]>siz[son[u]])
            son[u]=v.en;
        siz[u]+=siz[v.en];
    }
}
void dfs2(int u,int f,int id)
{
    top[u]=id;
    if(!son[u]) return;
    dfs2(son[u],u,id);
    for(int i=0;i<V[u].size();i++)
    {
        node v=V[u][i];
        if(v.en==f||v.en==son[u]) continue;
        dfs2(v.en,u,v.en);
    }
}
int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
        swap(u,v);
    return v;
}
int main()
{
    int t,o=0;
    int x,y,z;
    int a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        clr();
        scanf("%d%d",&n,&q);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            V[x].push_back(node(y,z));
            V[y].push_back(node(x,z));
        }
        dfs1(1,0,1);
        dfs2(1,0,1);
        scanf("%d%d%d",&a,&b,&c);
        printf("Case #%d:\n",++o);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            int d1=dis[x]+dis[y]-2*dis[LCA(x,y)];
            int d2=dis[x]+dis[a]-2*dis[LCA(x,a)]+dis[y]+dis[b]-2*dis[LCA(y,b)]+c;
            int d3=dis[x]+dis[b]-2*dis[LCA(x,b)]+dis[y]+dis[a]-2*dis[LCA(y,a)]+c;
            d2=min(d2,d3);
            printf("%d\n",d1-d2<0?0:d1-d2);
        }
    }
    return 0;
}