2019CSUST集训队选拔赛题解（二）

凛冬将至

Description

维斯特洛大陆的原住民是森林之子，他们长得如孩童一般，善于使用石器，威力值35，用树叶树枝作为衣物，在森林里繁衍生息，与万物和平相处。他们会使用古老的魔法（比如绿之视野），威力值55。后来先民从维斯特洛大陆架登陆，凭借手中的青铜兵器和战马大举入侵，威力值分别是35和55。森林之子凭借魔法顽强抵抗，并冒险利用龙晶制造出了一个神奇的强悍的物种——异鬼，威力值60。双方持久不下之时签订了和平协议，先民占据了维斯特洛大陆，森林之子只保有森林。

七大王国如火如荼兴起之时，在遥远海洋的另一端，一个神秘的家族悄然兴起——坦格利安家族。此家族拥有三条巨龙，威力值90+，经过一个世纪的备战，在领导者伊耿一世的带领下乘龙入侵维斯特洛大陆。

借助龙的力量，伊耿一世很快统一了维斯特洛的七大王国，建立了空前强大的坦格利安王朝，像所有外来入侵者一样，坦格利安家族摒弃了龙的信仰开始信仰七神，并且将龙由放养改为圈养，再加上坦格利安家族为了保持血统纯正，实行近亲婚姻，生出来的继承者精神病人越来越多，这导让坦格利安王朝开始了眼花缭乱的花样作死之旅。

众(wo)所(xia)周(che)知(de)，当凯特琳·徒利得知自己女儿艾莉亚逃到赫伦堡后，非常担心女儿的安全。假设维斯特洛大陆共有n个城市，共有n−1条双向道路把这n个城市连接起来。也就是说这是一棵树。凯特琳想尽快临冬城赶到赫伦堡。除了已知的n-1条边外，凯特琳还知道一条额外的秘密路径(也是双向的)：端点是是城市x和城市y，路径长度是z。现在想考考寒假过后的你有没有刷过题，问你Q个问题，每个问题给出临冬城(凯特琳所在城市)和赫伦堡(艾莉亚所在城市)的坐标，请你告诉凯特琳从临冬城到赫伦堡的最短路径长度是多少？

Input

第一行一个整数n(1≤n≤100000)。

以下n−1行描述一颗树，每行u,v,w表示一条从u到v长为w的路径，u!=v。

下一行三个整数x,y,z，意义如题（1≤x,y≤n,x!=y）。

下一行一个整数Q(100000)。

以下Q行两个数字U,V代表临冬城和赫伦堡的坐标。

1≤w,z≤10000

Output

对每次询问输出从临冬城到赫伦堡的最短路径长度。

题目中所描述的是一颗树

这里再提一下树的特点：

①每个点都联通

②不含圈

③n阶树有n-1条边

PS：特别的是，具备以上任何两个特点可推出第三个

要注意求树上两点的距离不能用最短路算法，一般用LCA（只会这个

该题在树的基础上另加了一条边只需要分情况讨论这条边对原有树的影响即可

故该题解法：裸LCA+分类讨论

ACODE:

//

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<string>

#include<queue>

#include<utility>

#include<vector>

#define lson l , m , rt << 1

#define rson m+1 , r , rt << 1 | 1

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const double pi = 3.1415926535;

const double eps = 1e-;

const int MX = 1e5 + ;

const int maxbit = ;

const double val = pi/180.0;

const int INF = 0x3f3f3f3f;

struct edge

{

    int to;

    int val;

};

int father[MX][maxbit];

int depth[MX];

int dis[MX];

int lg[MX];

vector<edge> G[MX];

void dfs(int nowp,int fa)

{

    depth[nowp] = depth[fa] + ;

    father[nowp][] = fa;

    for(int j = ;j <= lg[depth[nowp]] + ;++j)

    {

        father[nowp][j] = father[father[nowp][j-]][j-];

    }

    for(int i = ;i < G[nowp].size();++i)

    {

        edge e  = G[nowp][i];

        if(e.to != fa)

        {

            dis[e.to] = dis[nowp] + e.val;

            dfs(e.to,nowp);

        }

    }

}

int lca (int u,int v)

{

    if(depth[u] < depth[v]) swap(u,v);

    while(depth[u] != depth[v])

        u = father[u][lg[depth[u] - depth[v]]];

    if(u == v) return u;

    for(int j = lg[depth[u]];j >= ;--j)

    {

        if(father[u][j] != father[v][j]){

            u = father[u][j];

            v = father[v][j];

        }

    }

    return father[u][];

}

//对大常数的优化

void init()

{

    lg[] = -;

    for(int i = ;i < MX;++i) lg[i] = lg[i >> ] + ;

}

int main(int argc, char const *argv[])

{

    int n;

    int u,v,w;

    init();//记得初始化

    scanf("%d",&n);

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

    {

        scanf("%d%d%d",&u,&v,&w);

        //邻接表建图

        G[u].push_back({v,w});

        G[v].push_back({u,w});

    }

    dfs(,);

    scanf("%d%d%d",&u,&v,&w);

    int m;

    scanf("%d",&m);

    while(m--)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        //三种情况

        int p = lca(x,y);

        int ans = (dis[x] - dis[p]) + (dis[y] - dis[p]);

        int p1 = lca(x,u);

        int p2 = lca(y,v);

        int alt1 = (dis[x] - dis[p1]) + (dis[u] - dis[p1]);

        int alt2 = (dis[y] - dis[p2]) + (dis[v] - dis[p2]);

        ans = min(ans,alt1 + alt2 + w);

        p1 = lca(x,v);

        p2 = lca(y,u);

        alt1 = (dis[x] - dis[p1]) + (dis[v] - dis[p1]);

        alt2 = (dis[y] - dis[p2]) + (dis[u] - dis[p2]);

        ans = min(ans,alt1 + alt2 + w);

        printf("%d\n",ans);

    }

    return ;

}

以后千万不能带个错误的LCA板子了

巴特西

2019CSUST集训队选拔赛题解（二）

最新文章

热门文章