题目描述
一棵树，有边权，树上有若干条链，找某一条边长设为0，
可以让新的最长链的长度最小，求这个最小值。
点和链的个数上限在30万
样例
算法1
(暴力枚举) $O(nm)$
尝试树上每一条边的边长临时设为0，统计每条链的长度的最大值，
用于刷新答案的最小值。
考虑该边是否在某条链上，这个询问也是很难处理的。
还有，30万的规模明显不现实。
算法2
(二分答案) $O(nlogn)$
30万，常数不控制好，会超时1个点
二分这个最小值mid，看是否可以满足条件。
将长度超过mid的链标记出来，利用树上差分（边权）（需要dfs），
将公共边找出来，要设为0的边肯定在公共边上，
否则没有被影响到的链长度不变，还是大于mid，肯定是不行的，
换句话说，若找不到公共边则check为false；
若存在公共边（肯定在初始最长链上，而且肯定是连续的若干条边），
则找其中最长的一条边，让最长链减去该值，看结果是否小于等于mid，
若可以，则check为true（因为最长的减去该值都已经满足了，
其他更小一点的肯定也能满足），
否则check为false。
这个过程中dfs的O(n)是不能避免的，每条链的端点为树上差分标记O(m)
二分是O(max)
总计O(nlogn)
//因为采用dfsn递归求解树上差分的前缀和，效率低，所以过了19/20个点，后面程序改进了可以全过
#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;
vector<pair<int, int> > a[N]; //原始边
int b[N], d[N], fadis[N], f[N][M]; //距根长度, 深度, 与父结点距离, 倍增数组
struct Info{
int x, y, cofa, nodes, len; //最近公共祖先，两点之间的点数、长度
}edge[N]; //原始链起点终点及求得数据
int treesub[N]; //树上差分（边权）及前缀和
int n, m;
void dfs(int x, int fa){
for(UI i = 0; i < a[x].si; i++){
int y = a[x][i].fi, z = a[x][i].se;
if(y == fa) continue;
b[y] = b[x] + z, d[y] = d[x] + 1; //距根长度、深度（根的深度为0）
fadis[y] = z; //父结点距离
f[y][0] = x;
for(int j = 1; j < M; j++){
f[y][j] = f[f[y][j-1]][j-1];
} //更新倍增数组，为求lca准备
dfs(y, x);
}
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = M-1; i >= 0; i--){
if(d[f[x][i]] >= d[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = M-1; i >= 0; i--){
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
return a.len > b.len;
}
void dfsn(int x, int fa){ //树上差分（边权）的前缀和，表示该边被若干条链经过
for(UI i = 0; i < a[x].si; i++){
int y = a[x][i].fi, z = a[x][i].se;
if(y == fa) continue;
dfsn(y, x);
treesub[x] += treesub[y]; //y的子树前缀和累计至父结点x上
}
}
bool check(int va){ //如果答案是va，看是否能够满足，需要将链长超过va的链的公共边找出来
memset(treesub, 0, sizeof(treesub));
int comnums = 0; //有comnums条链长超过va，树上差分（边权）
for(int i = 1; i <= m && edge[i].len > va; i++){
comnums = i;
int x = edge[i].x, y = edge[i].y, z = edge[i].cofa;
treesub[x]++, treesub[y]++, treesub[z] -= 2; //树上差分（边权），记录该边被经过的次数
}
dfsn(1, 0); //求前缀和
for(int i = 1; i <= n; i++){
if(treesub[i] == comnums && edge[1].len - fadis[i] <= va){ //i号点向上的边是comnums条链的一条公共边
return true; //如果最长链去掉这条边可以使得链长不超过va（其他链去掉该边就更短了），可以满足
}
}
return false; //如果没有公共边，或者公共边不能让最长链长减少至不超过va，则不能满足
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i < n; i++){
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
a[x].push_back(make_pair(y, t));
a[y].push_back(make_pair(x, t));
}
dfs(1, 0);
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d %d", &x, &y);
int cofa = lca(x, y);
edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
}
sort(edge+1, edge+m+1, Mycomp); //按照链长度降序
int L = -1, R = edge[1].len; //-1是肯定不行的，最优情况是0，(L, R]的情况二分
while(L + 1 < R){
int mid = (L + R) >> 1;
if(check(mid)) R = mid; else L = mid;
}
printf("%d\n", R);
return 0;
}
//一开始就把dfs序列（先子后己）拿出来放入数组，求前缀和的时候遍历数组就很快了（比递归求快多了）
#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;
vector<pair<int, int> > a[N]; //原始边
int b[N], d[N], fadis[N], f[N][M]; //距根长度, 深度, 与父结点距离, 倍增数组
int dfsord[N], dfst = 0; //dfs序列（先子后己）
struct Info{
int x, y, cofa, nodes, len; //最近公共祖先，两点之间的点数、长度
}edge[N]; //原始链起点终点及求得数据
int treesub[N];
int n, m;
void dfs(int x, int fa){
for(UI i = 0; i < a[x].si; i++){
int y = a[x][i].fi, z = a[x][i].se;
if(y == fa) continue;
b[y] = b[x] + z, d[y] = d[x] + 1; //距根长度、深度（根的深度为0）
fadis[y] = z; //父结点距离
f[y][0] = x;
for(int j = 1; j < M; j++){
f[y][j] = f[f[y][j-1]][j-1];
} //更新倍增数组，为求lca准备
dfs(y, x);
}
dfsord[++dfst] = x; //dfs序列（先子后己）
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = M-1; i >= 0; i--){
if(d[f[x][i]] >= d[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = M-1; i >= 0; i--){
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
return a.len > b.len;
}
bool check(int va){ //如果答案是va，看是否能够满足，需要将链长超过va的链的公共边找出来
memset(treesub, 0, sizeof(treesub));
int comnums = 0; //有comnums条链长超过va，树上差分（边权）
for(int i = 1; i <= m && edge[i].len > va; i++){
comnums = i;
int x = edge[i].x, y = edge[i].y, z = edge[i].cofa;
treesub[x]++, treesub[y]++, treesub[z] -= 2;//树上差分（边权），记录该边被经过的次数
}
//求前缀和
for(int i = 1; i < n; i++){ //dfs序最后一个点是1，不需要贡献给父结点
int y = dfsord[i], x = f[y][0]; //dfs第i号点y, 其父结点x
treesub[x] += treesub[y]; //y的子树前缀和累计至父结点x上
} //树上差分（边权）的前缀和，表示该边被若干条链经过
for(int i = 1; i <= n; i++){
if(treesub[i] == comnums && edge[1].len - fadis[i] <= va){ //i号点向上的边是comnums条链的一条公共边
return true; //如果最长链去掉这条边可以使得链长不超过va（其他链去掉该边就更短了），可以满足
}
}
return false; //如果没有公共边，或者公共边不能让最长链长减少至不超过va，则不能满足
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i < n; i++){
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
a[x].push_back(make_pair(y, t));
a[y].push_back(make_pair(x, t));
}
dfs(1, 0);
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d %d", &x, &y);
int cofa = lca(x, y);
edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
}
sort(edge+1, edge+m+1, Mycomp); //按照链长度降序
int L = -1, R = edge[1].len; //-1是肯定不行的，最优情况是0，(L, R]的情况二分
while(L + 1 < R){
int mid = (L + R) >> 1;
if(check(mid)) R = mid; else L = mid;
}
printf("%d\n", R);
return 0;
}
算法3
(巧妙处理) $O(nlogn)$
将全部链根据长度降序
将最长链起点到终点重新编号，然后以起点为根遍历全部点，
若为最长链结点的子树，则该子树的全部结点编号为该结点相同编号，
则其他链的起点和终点的编号就和最长链经过的点形成的公共点同号。
比如：最长链经过1 2 3 4 ……n
某条其他链的起点是2的子树，则该起点编号就是2
终点是4的子树，则该终点编号就是4
该链与最长链的公共部分就是[2,4]
最终答案可能是最长链去掉最长边之后的值v1（该值不小于次长链的值v2）
如果去掉最长边之后的值v1小于v2，则答案可能是v2，
所以不能轻易说去掉那条边的值，应该是经过全部验证：
1、去掉最长链的最长边之后的值，与 v2 比较的较大值
2、去掉最长链和次长链的公共边的最大边之后的值，与次次长v3比较的较大值
3、去掉最长、次长、次次长的公共边的最大值，与v4比较。。。
。。。
如果某轮下来没有公共边了，则结束
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define si size()
#define UI unsigned int
using namespace std;
const int N = 3e5+10, M = 20;
vector<pair<int, int> > a[N]; //原始边
int b[N], d[N], f[N][M]; //距根长度, 深度, 倍增数组
struct Info{
int x, y, cofa, nodes, len; //最近公共祖先，两点之间的点数、长度
}edge[N]; //原始链起点终点及求得数据
int nord[N], nval[N]; //每个点的新编号，最长链的每条边的长度
int st[N][M]; //最长链的每条边长形成ST表为求RMQ
int n, m;
void dfs(int x, int fa){
for(UI i = 0; i < a[x].si; i++){
int y = a[x][i].fi, z = a[x][i].se;
if(y == fa) continue;
b[y] = b[x] + z, d[y] = d[x] + 1; //距根长度、深度（根的深度为0）
f[y][0] = x;
for(int j = 1; j < M; j++){
f[y][j] = f[f[y][j-1]][j-1];
} //更新倍增数组，为求lca准备
dfs(y, x);
}
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = M-1; i >= 0; i--){
if(d[f[x][i]] >= d[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = M-1; i >= 0; i--){
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
bool Mycomp(const Info&a, const Info&b){
return a.len > b.len;
}
void GetNordOfLink(){ //给最长边经过的点进行编号(1..)
int x = edge[1].x;
for(int i = 1; i <= d[edge[1].x] - d[edge[1].cofa] + 1; i++){
nord[x] = i;
x = f[x][0];
} //[x, lca]编号
int y = edge[1].y;
for(int i = edge[1].nodes; i > edge[1].nodes - (d[edge[1].y] - d[edge[1].cofa]); i--){
nord[y] = i;
y = f[y][0]; //(lca, y]编号
}
}
void dfsn(int x, int fa){
for(UI i = 0; i < a[x].si; i++){
int y = a[x][i].fi, z = a[x][i].se;
if(y == fa) continue;
if(!nord[y]) nord[y] = nord[x]; //形成新的编号
else nval[++nval[0]] = z; //是最长链的边，边数是点数少1，即edge[1].nodes-1，即nval[0]
dfsn(y, x);
}
}
void CreateST(int n){ //最长链的每条边长形成ST表为求RMQ
for(int i = 1; i <= n; i++) st[i][0] = nval[i];
int t = log(n) / log(2) + 1;
for(int j = 1; j < t; j++){
for(int i = 1; i <= n - (1<<j) + 1; i++){
st[i][j] = max(st[i][j-1], st[i + (1<<(j-1))][j-1]);
}
}
}
int ST_query(int l, int r){ //查询边长的最大值
int k = log(r - l + 1) / log(2);
return max(st[l][k], st[r - (1<<k) + 1][k]);
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i < n; i++){
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
a[x].push_back(make_pair(y, t));
a[y].push_back(make_pair(x, t));
}
dfs(1, 0);
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d %d", &x, &y);
int cofa = lca(x, y);
edge[i] = (Info){x, y, cofa, d[x] + d[y] - 2*d[cofa] + 1, b[x] + b[y] - 2*b[cofa]};
}
sort(edge+1, edge+m+1, Mycomp); //按照链长度降序
GetNordOfLink(); //给最长边经过的点进行编号(1..)
dfsn(edge[1].x, 0); //重新遍历整棵树形成每个点的新编号
//对于不是最长链上的点x，若挂在新编号i号结点上，则整个子树结点编号都设为i
CreateST(nval[0]); //对最长链的按顺序产生的边长做ST表为求RMQ
int ans = edge[1].len; //默认是最长链的长度
int L = 1, R = nval[0]+1;
for(int i = 1; i <= m ;i++){
int ll = nord[edge[i].x], rr = nord[edge[i].y];
if(ll > rr) swap(ll, rr); //取得第i长链的起点和终点，形成区间[ll, rr]
L = max(L, ll), R = min(R, rr); //更新[L, R]
if(R <= L) break; //如果公共边不存在，则结束
ans = min(ans, max(edge[1].len - ST_query(L, R-1), edge[i+1].len));
//找出公共边中最长的一条长度设为0，则第1~i条链都减少相同的值
//只要让最长链长减掉该值，和，第i+1条链长比较，取较大值刷新ans即可
}
printf("%d\n", ans);
return 0;
}
/*
输入样例：
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
输出样例：
11
*/
