题目背景
公元 2044 年,人类进入了宇宙纪元。
题目描述
公元 2044 年，人类进入了宇宙纪元
L 国有 nn 个星球，还有 n-1n−1 条双向航道，每条航道建立在两个星球之间，这 n-1n−1 条航道连通了 LL 国的所有星球。
小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_iui 号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 jj ，任意飞船驶过它所花费的时间为 t_jtj ，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 mm 个运输计划。在虫洞建设完成后，这 mm 个运输计划会同时开始，所有飞船一起出发。当这 mm 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？
输入输出格式
输入格式：
第一行包括两个正整数 n, mn,m ，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 11 到 nn 编号。
接下来 n-1n−1 行描述航道的建设情况，其中第 ii 行包含三个整数 a_i, b_iai,bi 和 t_iti ，表示第 ii 条双向航道修建在 a_iai 与 b_ibi 两个星球之间，任意飞船驶过它所花费的时间为 t_iti 。数据保证 1 \leq a_i,b_i \leq n1≤ai,bi≤n 且 0 \leq t_i \leq 10000≤ti≤1000 。
接下来 mm 行描述运输计划的情况，其中第 jj 行包含两个正整数 u_juj 和 v_jvj ，表示第 jj 个运输计划是从 u_juj 号星球飞往 v_jvj号星球。数据保证 1 \leq u_i,v_i \leq n1≤ui,vi≤n
输出格式：
输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
11 二分移动所需的时间，在二分出的时间里用树上倍增检验能否实现
看了题解还是调到吐血，最后发现m放在n后面直接读入了..
代码：
#include<algorithm>
#include<cstdio>
#include<cstring> const int Maxv = ;
int Book[Maxv], Head[Maxv], f[Maxv][], st[Maxv][], Top[Maxv], Tdis[Maxv], q[Maxv], rnum, tail, cnt, n, m;
bool lea[Maxv], vis[Maxv], fs; struct Node{
int u, v, w, next;
}e[Maxv << ]; struct Army{
int Rest, Top;
}army[Maxv]; int read(){
int x = , f = ;
char ch = getchar();
while (ch < '' || ch > '') {
if (ch == '-') {
f = -;
}
ch = getchar();
}
while (ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x * f;
} void Add_Edge(int u, int v, int w){
cnt++;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = Head[u];
Head[u] = cnt;
} void Add(int u, int v, int w){
Add_Edge(u, v, w);
Add_Edge(v, u, w);
} inline bool Cmp(int a, int b){
return a > b;
}
inline bool Cmpmin(Army a, Army b){
return a.Rest < b.Rest;
} inline bool Cmpmax(Army a, Army b){
return a.Rest > b.Rest;
} void dfs(int u, int father){
for (int i = Head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == father) {
continue;
}
f[v][] = u;
st[v][] = e[i].w;
dfs(v, u);
}
}//预处理倍增 void RMQ(){
for (int j = ; j <= ; j++) {
for (int i = ; i <= n; i++) {
f[i][j] = f[ f[i][j - ] ][j - ];
st[i][j] = st[i][j - ] + st[ f[i][j - ] ][j - ];
}
}
}//预处理倍增 void dfs1(int u, int father, int topf, int dist){
Top[u] = topf;
Tdis[u] = dist;
bool ft = false;
for (int i = Head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == father) {
continue;
}
ft = true;
dfs1(v, u, topf, dist);
}
if (!ft) {
lea[u] = true; //标记叶子节点
}
} void dfs2(int u, int father){
if (lea[u]) {
fs = true;
return;
}
for (int i = Head[u]; i; i = e[i].next) {
int v = e[i].v;
if (v == father) {
continue;
}
else if (vis[v]) {
continue;
}
dfs2(v, u);
if (fs) {
return;
}
}
} inline bool Look(int v){
fs = false;
dfs2(v, f[v][]);
return fs;
} inline bool judge(int mid){
memset(vis, false, sizeof(vis));
memset(q, , sizeof(q));
memset(army, , sizeof(army));
rnum = ;
tail = ;
for (int i = ; i <= m; i++) {
int tim = mid;
int now = Book[i];
bool syst = false;
while () {
for (int j = ; j >= ; j--) {
if (f[now][j] && st[now][j] <= tim) {
tim -= st[now][j];
now = f[now][j]; //向上跳
break;
}
if (j == || now == ) {
syst = true;
break; //停止条件
}
}
if (syst) {
break;
}
}
if (now == ) {
army[++rnum].Top = Top[ Book[i] ];
army[rnum].Rest = tim;
}
else {
vis[now] = true;
}
}
std::sort(army + , army + m + , Cmpmin);
for (int i = ; i <= m; i++) {
if (army[i].Rest < Tdis[ army[i].Top ]) {
if (!vis[ army[i].Top ] && Look(army[i].Top)) {
vis[ army[i].Top ] = true;
army[i].Rest = -;
}
}
}
std::sort(army + , army + m + , Cmpmax);
for (int i = Head[]; i; i = e[i].next) {
int v = e[i].v;
if (!vis[v] && Look(v)) {
q[++tail] = e[i].w;
}
}
std::sort(q + , q + tail + , Cmp);
for (int i = ; i <= tail; i++) {
if (army[i].Rest < q[i]) {
return false;
}
}
return true;
} int main(){
int u, v, w, R = , cnt1 = , Ans = ;
n = read(); for (int i = ; i < n; i++) {
u = read();
v = read();
w = read();
Add(u, v, w);
R += w;
}
dfs(, );
for (int i = Head[]; i; i = e[i].next) {
int v = e[i].v;
dfs1(v, , v, e[i].w);
}
RMQ();
m = read();
for (int i = ; i <= m; i++) {
Book[i] = read();
}
for (int i = Head[]; i; i = e[i].next) {
cnt1++;
}
if (cnt1 > m) {
printf("-1\n");
return ;
}
int L = ;
while (L <= R) {
int mid = (L + R) >> ;
if (judge(mid)) {
Ans = mid;
R = mid - ;
}
else {
L = mid + ;
}
}
printf("%d\n", Ans);
return ;
}