当前位置：网站首页>codevs 2370 小机房的树（LCA）

codevs 2370 小机房的树（LCA）

2022-08-10 11:07:00 【51CTO】

Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

Input Description

第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。(1<=n<=50000， 1<=m<=75000， 0<=c<=1000)
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点

Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

Sample Input

Sample Output

思路

LCA 问题，我们为每个点设置一个权值 tim[i] 等于从根节点到其路径中所有边权的和，于是虫子所要爬行的最短路径权值为 tim[u]+tim[v]-2*tim[lca(u,v)] 。

采用离线 tarjan 算法可以解决这一问题，每条边的权值我们可以将其保存在子节点中。

不过缺点就是离线算法不能保证计算顺序与输入顺序的一致，因此我们采用一个变量来标记每个查询的序号，得出所有结果后根据该序号排序后输出。

AC 代码

       
       #include<iostream>
       
       #include<vector>
       
       #include<cstring>
       
       #include<algorithm>
       
       #include<cstdio>
       
       using 
       
       namespace 
       
       std;
       
       typedef 
       
       pair
       
       <
       
       int,
       
       int
       
       > 
       
       P;
       
       const 
       
       int 
       
       maxn
       
       =
       
       51000;
       
       int 
       
       fa[
       
       maxn];
       
       int 
       
       rk[
       
       maxn];
       
       bool 
       
       visit[
       
       maxn];
       
       int 
       
       tim[
       
       maxn];              
       
       //将 u->v 路径权值存储在 v 中
       
       vector
       
       <
       
       int
       
       > 
       
       tree[
       
       maxn];
       
       vector
       
       <
       
       P
       
       > 
       
       Qes[
       
       maxn];
       
       vector
       
       <
       
       P
       
       > 
       
       ans;
       
       int 
       
       ancestor[
       
       maxn];
       
       struct 
       
       node
       
{
       
       int 
       
       to;
       
       int 
       
       next;
       
       int 
       
       cost;
       
} 
       
       edge[
       
       maxn
       
       <<
       
       1];
       
       int 
       
       head[
       
       maxn
       
       <<
       
       1],
       
       tot;
       
       void 
       
       addedge(
       
       int 
       
       u,
       
       int 
       
       v,
       
       int 
       
       cost)
       
{
       
       edge[
       
       tot].
       
       to
       
       =
       
       v;
       
       edge[
       
       tot].
       
       next
       
       =
       
       head[
       
       u];
       
       edge[
       
       tot].
       
       cost
       
       =
       
       cost;
       
       head[
       
       u]
       
       =
       
       tot
       
       ++;
       
}
       
       void 
       
       init(
       
       int 
       
       n)
       
{
       
       memset(
       
       rk,
       
       0,
       
       sizeof(
       
       rk));
       
       memset(
       
       visit,
       
       false,
       
       sizeof(
       
       visit));
       
       memset(
       
       ancestor,
       
       0,
       
       sizeof(
       
       ancestor));
       
       memset(
       
       tim,
       
       0,
       
       sizeof(
       
       tim));
       
       memset(
       
       head,
       
       -
       
       1,
       
       sizeof(
       
       head));
       
       tot
       
       =
       
       0;
       
       ans.
       
       clear();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
    {
       
       fa[
       
       i]
       
       =
       
       i;
       
       tree[
       
       i].
       
       clear();
       
       Qes[
       
       i].
       
       clear();
       
    }
       
}
       
       int 
       
       find_set(
       
       int 
       
       x)     
       
       //并查集 查询+路径压缩
       
{
       
       if(
       
       x
       
       !=
       
       fa[
       
       x])
       
       fa[
       
       x]
       
       =
       
       find_set(
       
       fa[
       
       x]);
       
       return 
       
       fa[
       
       x];
       
}
       
       void 
       
       union_set(
       
       int 
       
       x,
       
       int 
       
       y)     
       
       //并查集 合并
       
{
       
       x
       
       =
       
       find_set(
       
       x);
       
       y
       
       =
       
       find_set(
       
       y);
       
       if(
       
       rk[
       
       x]
       
       >
       
       rk[
       
       y])
       
       fa[
       
       y]
       
       =
       
       x;
       
       else
       
    {
       
       fa[
       
       x]
       
       =
       
       y;
       
       if(
       
       rk[
       
       x]
       
       ==
       
       rk[
       
       y])
       
       rk[
       
       y]
       
       ++;
       
    }
       
}
       
       void 
       
       LCA(
       
       int 
       
       u,
       
       int 
       
       pa,
       
       int 
       
       cost)
       
{
       
       ancestor[
       
       u]
       
       =
       
       u;
       
       tim[
       
       u]
       
       +=
       
       cost
       
       +
       
       tim[
       
       pa];       
       
       // u 点权值 = 父节点权值 + 边权值
       
       for(
       
       int 
       
       i
       
       =
       
       head[
       
       u]; 
       
       i
       
       !=-
       
       1; 
       
       i
       
       =
       
       edge[
       
       i].
       
       next)
       
    {
       
       int 
       
       to
       
       =
       
       edge[
       
       i].
       
       to;
       
       if(
       
       to
       
       ==
       
       pa)
       
       continue;
       
       LCA(
       
       to,
       
       u,
       
       edge[
       
       i].
       
       cost);
       
       union_set(
       
       u,
       
       to);
       
       ancestor[
       
       find_set(
       
       u)]
       
       =
       
       u;
       
    }
       
       visit[
       
       u]
       
       =
       
       true;
       
       int 
       
       len 
       
       = 
       
       Qes[
       
       u].
       
       size();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       len; 
       
       i
       
       ++)
       
       if(
       
       visit[
       
       Qes[
       
       u][
       
       i].
       
       second])
       
        {
       
       int 
       
       anc
       
       =
       
       ancestor[
       
       find_set(
       
       Qes[
       
       u][
       
       i].
       
       second)];
       
       ans.
       
       push_back(
       
       P(
       
       Qes[
       
       u][
       
       i].
       
       first,
       
       tim[
       
       u]
       
       +
       
       tim[
       
       Qes[
       
       u][
       
       i].
       
       second]
       
       -
       
       2
       
       *
       
       tim[
       
       anc]));
       
        }
       
}
       
       int 
       
       main()
       
{
       
       ios::sync_with_stdio(
       
       false);
       
       int 
       
       n,
       
       m;
       
       while(
       
       cin
       
       >>
       
       n)
       
    {
       
       init(
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       1; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
        {
       
       int 
       
       u,
       
       v,
       
       cost;
       
       cin
       
       >>
       
       u
       
       >>
       
       v
       
       >>
       
       cost;
       
       addedge(
       
       u,
       
       v,
       
       cost);
       
       addedge(
       
       v,
       
       u,
       
       cost);
       
        }
       
       cin
       
       >>
       
       m;
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       m; 
       
       i
       
       ++)
       
        {
       
       int 
       
       u,
       
       v;
       
       cin
       
       >>
       
       u
       
       >>
       
       v;
       
       Qes[
       
       u].
       
       push_back(
       
       P(
       
       i,
       
       v));       
       
       //其中 i 标记其输入的序号
       
       Qes[
       
       v].
       
       push_back(
       
       P(
       
       i,
       
       u));
       
        }
       
       LCA(
       
       0,
       
       -
       
       1,
       
       0);
       
       sort(
       
       ans.
       
       begin(),
       
       ans.
       
       end());        
       
       //因为 tarjan 离线算法不能保证计算和输入顺序一致
       
       int 
       
       len
       
       =
       
       ans.
       
       size();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       len; 
       
       i
       
       ++)
       
       cout
       
       <<
       
       ans[
       
       i].
       
       second
       
       <<
       
       endl;
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.