UPC2021个人训练赛第39场 C: 粉兔找妹子(换根dp)

简介: UPC2021个人训练赛第39场 C: 粉兔找妹子(换根dp)

问题 C: 粉兔找妹子

时间限制: 1 Sec 内存限制: 128 MB


题目描述

粉兔的妹子跑了!


于是,粉兔要去找她跑掉的妹子!


粉兔的妹子在福州某中上学 。


福州某中共有 N 个路口 ,编号从 1 到 N。路口之间由 N−1 条双向通行的道路连接,并且任意两个路口之间都是连通的。所有只有一条道路与之连接的路口都是福州某中的出入口。一些路口旁有教学楼。粉兔的妹子每天会从某个入口进去,到某栋教学楼上课,然后再从某个出口离开福州某中 。


由于妹子热爱锻炼身♂体, 所以他总是想使自己一天中走的总路程尽量长。当然,妹子不喜欢走重复的路,所以每天他都不会经过同一条路两次。也就是说,妹子会选择一对出入口使得从到教学楼、出口的距离和最大,并且两条路径不会经过同一条道路。可以证明,在不重复经过同一条道路的前提下,连接两个路口的路径是唯一的,从而它们间的距离也是唯一的。


粉兔通过某种手段控制了福州某中所有教学楼里的监摄像头,并掌握了每天妹子上课的教学楼。现在她想知道,妹子每天分别走了多长的路?


注意两个相同路口的距离为 0。

输入

第一行两个整数 N 和 M,分别表示福州某中的路口个数和总天数。

接下来 N−1 行,每行三个整数,Si,Ti和 Li,代表一条连接路口 Si 和 Ti、长度为 Li的道路 。

接下来 M 行,每一个整数 Ai,代表妹子第 i 天上课的教学楼旁路口编号。

输入数据保证合法。

输出

输出 M 行,分别代表妹子每一天走的路程之和。

样例输入 Copy

8 3

1 2 2

2 3 4

3 4 1

4 5 7

4 6 3

2 7 5

1 8 6

3

6

7

样例输出 Copy

20

16

17

提示

20200401134307494.png

对于3号路口,粉兔的妹子会选择从5号入口出发,依次经过路口4,3,2,1走到8号出口(反着走也可以),总长度:7+1+4+2+6=20;

对于6号路口,妹子选择的路径为6→4→3→2→1→8,总长度:3+1+4+2+6=16;

对于7号路口,妹子选择的路径为7→2→3→4→5,总长度:5+4+1+7=17。

对于全部数据, 2≤N≤5×1 0 5 10^510 5,1≤M≤1 0 5 10^5105,1≤Si,Ti,Ai≤N,1≤Li≤1 0 3 10^3103。

题意:

给出一棵点数为5 e 5的带权树,1 e 5次询问,每次询问经过x节点的最长路径(最长指的是权值和最大);

思路:

首先要了解用树形D P求树的直径的思路,本题跟其思路相近。

用d p [ u ] [ 0 ]表示从u到以u的子树里的最长距离;

d p [ u ] [ 1 ]表示从u到以u的子树里的次长距离;

根据树形D P的d f s我们就可以处理出这些。

考虑最长路径跟d p数组有什么关系?d p数组仅仅是针对子树里的,也就是向下扩展的,而最长路径还可以向上扩展。所以,我们再从根节点d f s一遍,求经过每个点的最长路径,最后O ( 1 )查询。

首先,根节点的d p一定是他本身的答案,因为对于根节点,我们遍历了他所有的节点;而其他节点,只遍历了从根节点到该节点方向的节点;

从根节点向下递推,假设现在正在更新v节点,而v的父亲节点u节点已经被更新过了,那么先要考虑u节点的最长路径是否经过v节点,如果经过的话,只能用u节点的次长路径去更新v;不经过的话,用u节点的最长路径去更新v,这就是换根的过程。

比如样例中的,假设根节点为1(无根树可以任意指定一个节点作为根节点)。现在d p 数组的值已经通过d f s 1求出来了。

最长距离 次长距离
1 14 6
2 12 5

从1推向2,可以发现d p [ 2 ] [ 0 ] + w = d p [ 1 ] [ 0 ],也就是说1到子树里的最长路径经过2,所以只能用1到子树里的最长路径去更新2,注意还要加上1 , 2的边的权值。

更新完后2的最长距离为12,次长距离为8,两者相加就是经过2的最长路径。

代码:

const int maxn=1e6+7;
vector<PLL>g[maxn];
ll dp[maxn][2],ans[maxn],n,m;
void dfs1(int u,int fa){
  dp[u][0]=dp[u][1]=0;
  for(auto t:g[u]){
    ll nex=t.first,w=t.second;
    if(nex==fa) continue;
    dfs1(nex,u);
    if(dp[u][0]<dp[nex][0]+w){
      dp[u][1]=dp[u][0];
      dp[u][0]=dp[nex][0]+w;
    }
    else if(dp[u][1]<dp[nex][0]+w){
      dp[u][1]=dp[nex][0]+w;
    }
  }
}
void dfs2(int u,int fa){
  for(auto t:g[u]){
    ll v=t.first,w=t.second;
    if(v==fa) continue;
    if(dp[v][0]+w==dp[u][0]){
      ll d=w+dp[u][1];
      if(dp[v][0]<d){
        dp[v][1]=dp[v][0];
        dp[v][0]=d;
      }
      else if(dp[v][1]<d){
        dp[v][1]=d;
      }
    }
    else{
      ll d=w+dp[u][0];
      if(dp[v][0]<d){
        dp[v][1]=dp[v][0];
        dp[v][0]=d;
      }
      else if(dp[v][1]<d){
        dp[v][1]=d;
      }
    }
    ans[v]=dp[v][0]+dp[v][1];
    dfs2(v,u);
  }
}
int main(){
  n=read,m=read;
  rep(i,1,n-1){
    ll u=read,v=read,w=read;
    g[u].push_back({v,w});
    g[v].push_back({u,w});
  }
  dfs1(1,-1);
  ans[1]=dp[1][0]+dp[1][1];
  dfs2(1,-1);
  while(m--){
    int x=read;
    printf("%lld\n",ans[x]);
  }
  return 0;
}
目录
相关文章
|
6月前
|
Java
leetcode-452:用最少数量的箭引爆气球
leetcode-452:用最少数量的箭引爆气球
61 0
|
机器学习/深度学习
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
85 0
|
人工智能
upc 2021级新生个人训练赛第53场(珂朵莉与数字,珂朵莉与序列,珂朵莉与字符串,珂朵莉与面积)
upc 2021级新生个人训练赛第53场(珂朵莉与数字,珂朵莉与序列,珂朵莉与字符串,珂朵莉与面积)
94 0
|
编译器 C++ 容器
C++/PTA 气球升起来
程序设计竞赛时,赛场升起各色气球多么激动人心呀!志愿者送气球忙得不亦乐乎,观战的某人想知道目前哪种颜色的气球送出最多。
147 0
|
人工智能 BI
【每日一题Day25】LC790多米诺和托米诺平铺 | 状态机DP
有两种形状的瓷砖:一种是 2 x 1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
105 0
【每日一题Day25】LC790多米诺和托米诺平铺 | 状态机DP
|
存储
UPC组队第三场——K: A Famous Grid (BFS+细节)
UPC组队第三场——K: A Famous Grid (BFS+细节)
83 0
UPC组队第三场——K: A Famous Grid (BFS+细节)
|
人工智能 BI
upc-2021个人训练赛第27场 D: Values(思维+并查集)
upc-2021个人训练赛第27场 D: Values(思维+并查集)
81 0
|
人工智能
upc2021个人训练赛第23场M: 紫罗兰(dsu)
upc2021个人训练赛第23场M: 紫罗兰(dsu)
95 0
|
机器人
UPC—— 最勇敢的机器人(并查集+分组背包)
UPC—— 最勇敢的机器人(并查集+分组背包)
78 0
upc2021个人训练赛第22场A. 联通数(思维)
upc2021个人训练赛第22场A. 联通数(思维)
55 0