Journey

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/92

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≤105) and Q(1≤Q≤105), 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 xth city and the yth city, the first N−1 roads will form a tree structure, indicating the original roads, and the Nth 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 xth city to yth 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 ith line contains one integer indicating the time could saved in ith journey plan.

Sample Input

Sample Output

Case #1:

0

2

0

2

2

HINT

题意

给你一棵树，然后加了一条边，然后给Q次询问，问你这些点之间的最短距离缩短了多少

题解：

加了边之后，你走的方式就变成三种了，要么和原来一样，要么就是u-A-B-v,要么就是u-B-A-v这种

tarjan预处理一下距离跑一发就好了

代码：

//qscqesze

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200006

#define mod 1000000007

#define eps 1e-9

#define e exp(1.0)

#define PI acos(-1)

const double EP  = 1E- ;

int Num;

//const int inf=0x7fffffff;

const ll inf=;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//***********************************************************

struct ndoe{

    int v,w,next;

}ed[maxn*];

int dp[][maxn*],pos[maxn],dis[maxn],res[maxn],head[maxn],parent[maxn],vis[maxn];

int n,m,c,num,cnt,size;

void addedge(int u,int v,int w)

{

    ed[num].v=v;

    ed[num].w=w;

    ed[num].next=head[u];

    head[u]=num++;

}

int Find(int i)

{

    if(i!=parent[i])

        parent[i]=Find(parent[i]);

    return parent[i];

}

void Union(int i,int j)

{

    int x,y;

    x=Find(i);

    y=Find(j);

    if(x!=y)

        parent[x]=y;

}

int A,B,C,q;

void init()

{

    int i,j,k;

    n=read();q=read();

    m=n-;

    memset(head,-,sizeof(head));

    memset(vis,,sizeof(vis));

    for(i=;i<=n;i++)

        parent[i]=i;

    cnt=size=num=;

    while(m--)

    {

        scanf("%d%d%d",&i,&j,&k);

        addedge(i,j,k);

        addedge(j,i,k);

        Union(i,j);

    }

    A=read(),B=read(),C=read();

}

void dfs(int u,int dist)

{

    int i,j;

    vis[u]=;

    dis[u]=dist;

    pos[u]=cnt;

    res[size]=u;

    dp[][cnt++]=size++;

    for(i=head[u];i!=-;i=ed[i].next)

    {

        j=ed[i].v;

        if(!vis[j])

        {

            dfs(j,dist+ed[i].w);

            dp[][cnt++]=dp[][pos[u]];

        }

    }

}

void rmq()

{

    int i,j,k;

    for(i=;(<<i)<=n;i++)

        for(j=n-;j>=;j--)

        {

            k=(<<(i-));

            dp[i][j]=dp[i-][j];

            if(k+j<n)

                dp[i][j]=min(dp[i][j],dp[i-][j+k]);

        }

}

int cal(int i,int j)

{

    int k;

    if(i<j)

    {

        i^=j;

        j^=i;

        i^=j;

    }

    k=;

    while((<<k)<=(i-j+))

        k++;

    k--;

    k=min(dp[k][j],dp[k][i-(<<k)+]);

    return res[k];

}

int Dis(int u,int v)

{

    int k = cal(pos[u],pos[v]);

    return dis[u]+dis[v]-dis[k]*;

}

int tot = ;

void solve()

{

    int i,j,k;

    for(i=;i<=n;i++)

        if(!vis[i])

            dfs(i,);

    n=n*-;

    rmq();

    printf("Case #%d:\n",tot);

    for(int i=;i<=q;i++)

    {

        int u=read(),v=read();

        int P = Dis(u,v);

        int PP1 = Dis(u,A)+C+Dis(B,v);

        int PP2 = Dis(u,B)+C+Dis(A,v);

        PP1 = min(PP1,PP2);

        printf("%d\n",max(P-PP1,));

    }

}

int main()

{

    int t=read();

    while(t--)

    {

        tot++;

        init();

        solve();

    }

    return ;

}

秒客网

cdoj 92 Journey tarjan/lca 树上点对距离