博客观赏效果更佳

题意简述

$n$个点的边带权树，给$m$条关键的链。把树上一条边的权值变为0，使得$m$条链的和中，最大值最小。 $n,m<=1e5$。

思路

二分最大值$k$。现在考虑如何检验一个$k$。

找到所有链和$>k$的链，设这里面最长的链长度为$S$，有$C$条这样的链。用树链剖分找到被所有$C$条链都覆盖的边。设边权为$w$，如果$S-w<=k$，又因为这条边被所有和$>k$的链都覆盖了，所以，将这条边边权设为$0$，就珂以把所有和$>k$的链修♂正回来。那就满足条件了，检验结果为true。

然后就这样二分即珂。

关于如何求被所有链都覆盖的边

如果您足够明智，跳过这个部分好了。

开一颗临时的树，所有边权为$0$，树链剖分维护：对于所有和$>k$的链$(a,b)$，在链上的边权都+1。

然后只要找边权$=C$的边即珂。

但是树链剖分维护的是点权，怎么把边权转化成点权呢？只要把一条边的权值，记录在这条边的儿子上即珂。然后我们对于链$(u,v)$作加法操作的时候，记得把$LCA(u,v)$的操作给撤回掉（就是减掉），因为这个是多算的。

代码

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{#define int long long #define N 355555#define F(i,l,r) for(int i=l;i<=r;++i)#define D(i,r,l) for(int i=r;i>=l;--i)#define Fs(i,l,r,c) for(int i=l;i<=r;c)#define Ds(i,r,l,c) for(int i=r;i>=l;c)#define MEM(x,a) memset(x,a,sizeof(x))#define FK(x) MEM(x,0)#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))#define p_b push_back#define sz(a) ((int)a.size())#define iter(a,p) (a.begin()+p)class Graph //图{public:int head[N];int EdgeCount;struct Edge{int To,Label,Next;}Ed[N<<1];void clear(int _V=N,int _E=N<<1) {memset(Ed,-1,sizeof(Edge)*(_E));memset(head,-1,sizeof(int)*(_V));EdgeCount=-1;}void AddEdge(int u,int v,int w=1){Ed[++EdgeCount]=(Edge){v,w,head[u]};head[u]=EdgeCount;}void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}int Start(int u) {return head[u];}int To(int u){return Ed[u].To;}int Label(int u){return Ed[u].Label;}int Next(int u){return Ed[u].Next;}}G;class BIT //树状数组{public:int tree[N];int len;void BuildTree(int _len){len=_len;FK(tree);}void Add(int pos,int val=1){for(int i=pos;i<=len;i+=(i&(-i))){tree[i]+=val;}}void RAdd(int l,int r,int val=1) {Add(l,val);Add(r+1,-val);}int Query(int pos){int ans=0;for(int i=pos;i>0;i-=(i&(-i))){ans+=tree[i];}return ans;}}T;void R1(int &x){x=0;char c=getchar();int f=1;while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();x=(f==1)?x:-x;}int n,m;int a[N],b[N];void Input(){R1(n),R1(m);G.clear();int u,v,w;F(i,1,n-1) R1(u),R1(v),R1(w),G.Add2(u,v,w);F(i,1,m) R1(a[i]),R1(b[i]);}int fa[N],deep[N],size[N],dis[N];int son[N],val[N]; //val[i]: i和fa[i]之间的边权，就是上面说的，“把边权记录在该边的儿子上”//dis[i]: i到根节点的带权距离（就是经过的所有边权的和）void DFS1(int u,int f){fa[u]=f; deep[u]=(u==f)?0:deep[f]+1;dis[u]=(u==f)?0:dis[f]+val[u]; size[u]=1;son[u]=-1;int Max=-1;Tra(i,u){int v=__v;if (v!=f){val[v]=G.Label(i);DFS1(v,u);size[u]+=size[v];if (size[v]>Max) {Max=size[v];son[u]=v;}}}}int DFSid[N],top[N],Time=0;void DFS2(int u,int topu){DFSid[u]=++Time;top[u]=topu;if (son[u]==-1) return;DFS2(son[u],topu);Tra(i,u){int v=__v;if (v!=fa[u] and v!=son[u]) DFS2(v,v);}}int LCA(int u,int v) //树剖求LCA （真的只是个LCA，没别的）{while(top[u]!=top[v]){if (deep[top[u]]<deep[top[v]]) swap(u,v);u=fa[top[u]]; }return deep[u]<deep[v]?u:v;}int PathLen(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];} //求链<u,v>的带权长度void PathAdd(int u,int v,int w=1){while(top[u]!=top[v]){if (deep[top[u]]<deep[top[v]]) swap(u,v);T.RAdd(DFSid[top[u]],DFSid[u],w);u=fa[top[u]];}if (deep[u]>deep[v]) swap(u,v);T.RAdd(DFSid[u],DFSid[v],1); //常规树剖操作int L=LCA(u,v);T.RAdd(DFSid[L],DFSid[L],-1); //把多算的减掉}int Maxlen;bool cxk(int k){T.BuildTree(n);int cnt=0;F(i,1,m) if (PathLen(a[i],b[i])>k) //如果这条边权值过大{++cnt;PathAdd(a[i],b[i],1);}F(i,1,n) {if (T.Query(DFSid[i])==cnt and Maxlen-val[i]<=k) // T.Query(DFSid[i])==cnt表示i和fa[i]这条边被所有的该修正的边覆盖了//Maxlen-val[i]<=k表示，我能修正所有该修正的边{return true; //所以这个时候把(i,fa[i])这条边权值设为0，就满足条件了。}}return false;}void Soviet(){DFS1(1,1);DFS2(1,1);Maxlen=-1; F(i,1,m) Maxlen=max(Maxlen,PathLen(a[i],b[i])); //Maxlen珂以提前求，少掉一个mT.BuildTree(n);int l=0,r=1e9; //注意：l=0（我一开始就是这样写的，没WA过，但是我猜写l=1会WA几个点）while(l<r){int mid=(l+r)>>1;if (cxk(mid)) r=mid;else l=mid+1;}printf("%lld\n",l);}#define Flan voidFlan IsMyWife(){Input();Soviet();}#undef int //long long 
}
int main(){Flandre_Scarlet::IsMyWife();getchar();getchar();return 0;
}