1.题面
2.前言
太妙了啊太妙了
3.分析
大体思路：枚举每一条边，每一条边都对应着两个点
(
u
,
v
)
(u, v)
(u,v) ，从这条边断开后，将出现以
u
u
u ,
v
v
v 为根节点的两颗树，我们就将这条边最大化利用，就是将在左子树的人尽可能多的移动到右子树去(这样一定会经过
e
d
g
e
(
u
,
v
)
edge(u, v)
edge(u,v) )，右子树同理，由于每个城市只能由一个人，所以在两颗树上的人交换过去的数量为两棵子树节点数量的最小值。
ATTENTION :为什么这样做不会出现一个人多次走一条边的情况呢？因为我们枚举的是边，假设的是让两棵树上的人交换，所以之后我们不会再遍历这条边了，又因为道路是一棵树，所以不会出现环，所以也不会出现走回原点的情况。
4.参考代码
#include <cstdio>
#include <cstring>
#define LL long long
const int MAXN
= 1e5 + 5;
int t
, n
;
LL ans
;
LL dp
[MAXN
];
int len
;
int head
[MAXN
];
struct edge
{
int to
, next
, val
;
}e
[MAXN
* 2];
void add
(int, int, int);
void dfs
(int, int);
void init
();
LL Min
(LL x
, LL y
) { return x
< y
? x
: y
; }
int main
() {
scanf
("%d", &t
);
while (t
--) {
init
();
scanf
("%d", &n
);
for (int i
= 1; i
< n
; i
++) {
int x
, y
, val
; scanf
("%d %d %d", &x
, &y
, &val
);
add
(x
, y
, val
); add
(y
, x
, val
);
}
dfs
(1, -1);
printf
("%lld\n", ans
);
}
return 0;
}
void init
() {
memset
(head
, 0, sizeof head
);
memset
(dp
, 0, sizeof dp
);
ans
= 0; len
= 0;
}
void add
(int x
, int y
, int val
) {
e
[++len
].to
= y
;
e
[len
].next
= head
[x
];
e
[len
].val
= val
;
head
[x
] = len
;
}
void dfs
(int u
, int father
) {
dp
[u
] = 1;
for (int i
= head
[u
]; i
; i
= e
[i
].next
) {
int v
= e
[i
].to
, w
= e
[i
].val
;
if (v
== father
) continue;
dfs
(v
, u
);
ans
+= 2 * w
* Min
(dp
[v
], n
- dp
[v
]);
dp
[u
] += dp
[v
];
}
}
