马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题目形貌
给定一个棵由编号为 1~n 这 n 个节点构成的树，及 m 个关键节点，树的第 i 条双向边连接 ui 和 vi ，长度为 wi 。你可以从树上任何一个节点出发开始游走，到任何一个节点结束，但整个游走过程中必须经过给定的 m 个关键节点。
叨教，应当如何计划路线，能够使得整个游走过程中，经过的路径长度最短。
输入格式
输入第一行，两个正整数 n,m
接下来 n−1 行，每行 3 个正整数，其中第 i+1 行分别表现第 i 条边的 ui，vi，wi。
输入最后行，m 个正整数，分别表现 m 个关键节点的编号 ci。
输出格式
输出共一行，表现所求最短长度。
数据范围
1≤m≤n≤1e5，1 ≤ ui，vi，ci ≤n， 1≤w ≤1e4
样例数据
输入:
5 3
1 2 2
2 3 4
2 4 5
1 5 1
3 4 5
输出:
15
阐明:
3–>2–>1–>5–>1–>2–>4
4 2 1 1 2 5
分析
树形dp + 换根
假设出发点为st，假设m个关键节点分布在st的k个子树内，则我们将只经过其中1个子树一次，然后别的k-1个子树的每条边经过两次。
一个很显然的贪婪是，为了使总旅程最短，我们应该满足 只经过1次的子树的旅程和 最大。
可以dfs来求
其中f代表从u节点访问u子树的所有关键点然后再返回u节点需要的总旅程（即所有路径均为两倍），
mx[0]和mx[1]分别表现i的子树的最大值和次大值。（至于为什么还需要维护次大值，后续会讲到）
- void dfs(int u,int fa){
- if(flag[u]) cnt[u] = 1;
- for(int i = h[u];i != -1;i = ne[i]){
- int j = e[i],val = w[i];
- if(j != fa){
- dfs(j,u);
-
- if(cnt[j]){
- cnt[u] += cnt[j];
- f[u] += f[j] + 2 * val;
- int tmp = mx[j][0] + val;
- if(tmp > mx[u][0]){
- mx[u][1] = mx[u][0],id[u][1] = id[u][0];
- mx[u][0] = tmp,id[u][0] = j;
- }else if(tmp > mx[u][1]){
- mx[u][1] = tmp,id[u][1] = j;
- }
- }
- }
- }
- }
可以采用换根dp来写
对于 u → j u \rightarrow j u→j 这条边，根从 u u u 转移到 j j j ，
若 j 子树内关键节点数为0，则 f[j] = f + 2 * val；
若 j 子树内关键节点数为m，则 f[j] 不变；
否则， f[j] = f 。
若 j 子树内关键节点数为m，则还需要更新mx[j][0]和mx[j][1]的值。（具体细节见代码）
- void dp(int u,int fa){
- res = min(res,f[u] - mx[u][0]);
- for(int i = h[u];i != -1;i = ne[i]){
- int j = e[i],val = w[i];
- if(j != fa){
- if(!cnt[j]) f[j] = f[u] + 2 * val;
- else if(cnt[j] == m) f[j] = f[j];
- else f[j] = f[u];
- if(cnt[j] != m){
- int tmp;
- if(id[u][0] == j) tmp = mx[u][1] + val;
- else tmp = mx[u][0] + val;
- if(tmp > mx[j][0]){
- mx[j][1] = mx[j][0],id[j][1] = id[j][0];
- mx[j][0] = tmp,id[j][0] = u;
- }else if(tmp > mx[j][1]){
- mx[j][1] = tmp,id[j][1] = u;
- }
- }
- dp(j,u);
- }
- }
- }
- #include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5 + 10;int n,m;bool flag[N];int h[N],e[N * 2],w[N * 2],ne[N * 2],idx;LL cnt[N],f[N],mx[N][2],id[N][2],res;void add(int a,int b,int c){ e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;}void dfs(int u,int fa){
- if(flag[u]) cnt[u] = 1;
- for(int i = h[u];i != -1;i = ne[i]){
- int j = e[i],val = w[i];
- if(j != fa){
- dfs(j,u);
-
- if(cnt[j]){
- cnt[u] += cnt[j];
- f[u] += f[j] + 2 * val;
- int tmp = mx[j][0] + val;
- if(tmp > mx[u][0]){
- mx[u][1] = mx[u][0],id[u][1] = id[u][0];
- mx[u][0] = tmp,id[u][0] = j;
- }else if(tmp > mx[u][1]){
- mx[u][1] = tmp,id[u][1] = j;
- }
- }
- }
- }
- }
- void dp(int u,int fa){
- res = min(res,f[u] - mx[u][0]);
- for(int i = h[u];i != -1;i = ne[i]){
- int j = e[i],val = w[i];
- if(j != fa){
- if(!cnt[j]) f[j] = f[u] + 2 * val;
- else if(cnt[j] == m) f[j] = f[j];
- else f[j] = f[u];
- if(cnt[j] != m){
- int tmp;
- if(id[u][0] == j) tmp = mx[u][1] + val;
- else tmp = mx[u][0] + val;
- if(tmp > mx[j][0]){
- mx[j][1] = mx[j][0],id[j][1] = id[j][0];
- mx[j][0] = tmp,id[j][0] = u;
- }else if(tmp > mx[j][1]){
- mx[j][1] = tmp,id[j][1] = u;
- }
- }
- dp(j,u);
- }
- }
- }
- int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); memset(h,-1,sizeof h); cin >> n >> m; for(int i = 0,u,v,w;i < n - 1;i++){ cin >> u >> v >> w; add(u,v,w),add(v,u,w); } for(int i = 1,j;i <= m;i++){ cin >> j; flag[j] = true; } dfs(1,-1); res = f[1] - mx[1][0]; dp(1,-1); cout << res; return 0;}
|
