Description
公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。如果小 P 可以*选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？
Input
第一行包括两个正整数 n,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 1 到 n 编号。接下来 n−1 行描述航道的建设情况，其中第 i 行包含三个整数 ai,bi 和 ti，表示第 i 条双向航道修建在 ai 与 bi 两个星球之间，任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n
Output
输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
Sample Input
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
Sample Output
11
Hint
将第 1 条航道改造成虫洞： 则三个计划耗时分别为：11,12,11，故需要花费的时间为 12。
将第 2 条航道改造成虫洞： 则三个计划耗时分别为：7,15,11，故需要花费的时间为 15。
将第 3 条航道改造成虫洞： 则三个计划耗时分别为：4,8,11，故需要花费的时间为 11。
将第 4 条航道改造成虫洞： 则三个计划耗时分别为：11,15,5，故需要花费的时间为 15。
将第 5 条航道改造成虫洞： 则三个计划耗时分别为：11,10,6，故需要花费的时间为 11。
故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短，需要花费的时间为 11。
(原题传送门[here])
首先需要求LCA，把所有询问的求的LCA和出发点，结束点保存下来。
然后二分答案。判断是否可以把耗时大于它的航线的用时缩短到小于等于二分值。
这个判定就用差分，先在数组中将LCA的值-2，出发点和结束点的值分别+1，从叶节点向上累加。
关于判定就找1个所有需要改的航线都覆盖了的边。并且使耗时的最大值要不超过二分值，这样样就行了。否则说明还会有航线的值大于二分值。
另外注意常数对算法的影响，理论复杂度O(n + m + nlog2L)。（L是树上最长链的长度）
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
} typedef class Edge{
public:
int end;
int next;
int w;
Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w){}
}Edge; typedef class MapManager{
public:
int ce;
int* h;
Edge* edge;
MapManager(){}
MapManager(int points, int edges):ce(){
h = new int[(const int)(points + )];
edge = new Edge[(const int)(edges + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int w){
edge[++ce] = Edge(end, h[from], w);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end, int w){
addEdge(from, end, w);
addEdge(end, from, w);
}
}MapManager; #define m_begin(g, i) (g).h[(i)]
#define m_end(g, i) (g).edge[(i)].end
#define m_next(g, i) (g).edge[(i)].next
#define m_w(g, i) (g).edge[(i)].w template<typename T>class Matrix{
public:
T *p;
int lines;
int rows;
Matrix():p(NULL){ }
Matrix(int lines, int rows):lines(lines), rows(rows){
p = new T[(lines * rows)];
}
T* operator [](int pos){
return (p + pos * lines);
}
};
#define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) typedef class union_found{
public:
int *f;
union_found():f(NULL) {}
union_found(int points) {
f = new int[(const int)(points + )];
}
int find(int x) {
if(f[x] != x) return f[x] = find(f[x]);
return f[x];
}
int& operator [](int pos){
return f[pos];
}
}union_found; #define BZ_MAX 19 typedef class query{
public:
int from;
int end;
int minv;
int lca;
query(const int from = , const int end = , const int lca = , const int minv = ):from(from), lca(lca), end(end), minv(minv){}
boolean operator <(query another) const {
return this->minv < another.minv;
} }query; boolean operator <(int val, query a){
return val < a.minv;
}
int n, q;
int cq;
int* times;
int* up;
int* dis;
MapManager g;
boolean* visited;
boolean* enable;
query *results;
MapManager mq;
union_found uf; inline void init(){
readInteger(n);
readInteger(q);
g = MapManager(n, * n);
mq = MapManager(n, * q);
for(int i = , a, b, c; i < n; i++){
readInteger(a);
readInteger(b);
readInteger(c);
g.addDoubleEdge(a, b, c);
}
for(int i = , a, b; i <= q; i++){
readInteger(a);
readInteger(b);
mq.addDoubleEdge(a, b, );
}
} void dfs(int node, int last, int distance){
up[node] = last;
dis[node] = distance;
for(int i = m_begin(g, node); i != ; i = m_next(g, i)){
int &e = m_end(g, i);
if(e == last) continue;
dfs(e, node, m_w(g, i) + distance);
}
} inline void init_dfs(){
up = new int[(const int)(n + )];
dis = new int[(const int)(n + )];
uf = union_found(n + );
visited = new boolean[(const int)(n + )];
enable = new boolean[(const int)(q * + )];
memset(up, , sizeof(int) * (n + ));
memset(enable, true, sizeof(boolean) * (q * + ));
memset(visited, false, sizeof(boolean) * (n + ));
dfs(, , );
} int cal_length(int a, int b, int lca){
return dis[a] + dis[b] - (dis[lca] << );
} void tarjan(int node){
uf[node] = node;
visited[node] = true;
for(int i = m_begin(g, node); i != ; i = m_next(g, i)){
int& e = m_end(g, i);
if(!visited[e]){
tarjan(e);
uf[e] = node;
}
}
for(int i = m_begin(mq, node); i != ; i = m_next(mq, i)){
int& e = m_end(mq, i);
if(visited[e] && enable[i]){
int lca = uf.find(e);
results[++cq] = query(node, e, lca, cal_length(node, e, lca));
enable[i] = enable[i + ((i & ) ? () : (-))] = false;
}
}
} boolean update(int node, int limit, int maxer, int minx){
for(int j = m_begin(g, node); j != ; j = m_next(g, j)){
int& e = m_end(g, j);
if(e == up[node]) continue;
if(update(e, limit, maxer, minx)) return true;
times[node] += times[e];
}
if(times[node] == limit){
if(maxer - cal_length(node, up[node], up[node]) <= minx){
return true;
}
}
return false;
} boolean check(int minx){
int counter = ;
int maxer = ;
memset(times, , sizeof(int) * (n + ));
query* it = upper_bound(results + , results + q + , minx);
for(; it != results + q + ; it++){
times[it->from]++;
times[it->end]++;
times[it->lca]++;
counter++;
smax(maxer, it->minv);
}
return update(, counter, maxer, minx);
} inline void solve(){
int l = , r;
results = new query[(const int)(q + )];
tarjan();
delete[] visited;
delete[] uf.f;
times = new int[(const int)(n + )];
sort(results + , results + q + );
r = results[q].minv;
while(l <= r){
int mid = l + ((r - l) >> );
if(check(mid)) r = mid - ;
else l = mid + ;
}
printf("%d", r + );
} int main(){
init();
init_dfs();
solve();
return ;
}
(PS:这道题很神奇，vijos过了，codevs的最后一个点TLE)