原题链接：P2680 运输计划
总结：树上差分入门好题。
题目大意：给出一棵$n$个点的树，边带边权；同时给出$m$条树上路径；允许将一条边的边权钦定修改为0，最小化路径的最大值。
考虑暴力，枚举每条边，将其边权暴力修改为0后统计答案。枚举边的复杂度为$O(n)$，暴力dfs统计答案需要枚举$m$条给出的路径，对每条路径暴力求长度，则复杂度为$O(nm)$，总复杂度为$O(n^2m)$，显然不可过，考虑求长度时可以前缀和优化，统计答案降至$O(m)$，则总复杂度为$O(nm)$，仍然不可过。
暴力显然已达极限，考虑换个思路。如果修改完后的最长路长度为$x$，那么对于长度大于$x$的所有路径，必然有一条长为$maxp$的公共边，使得原本的最长路径$maxd$满足$maxd - maxp = x$。于是我们惊讶地发现如果预先知道答案，则本题异常好做，故考虑二分答案，check函数只需将上式改写为$maxd - maxp \le x$即可，若满足条件则答案符合，不满足则答案不符合；对于满足条件的答案$x$，比$x$大的答案也一定符合，对于不满足条件的答案$x$，比$x$小的答案也一定不符合，答案满足单调性，二分答案可做。
进一步考虑check函数：我们可以找出所有长度大于$x$的路径，统计这些路径经过了哪些边，贪心地寻找这些路径都经过的一条权值最大的公共边，显然，修改这条边为0一定最优，记录一下这条边的权值$maxp$，然后用上面的式子判一下即可，复杂度$O(n+m)$。
修改前的最长路径可以在$O(n)$时间内求出，记为$maxd$，则总时间复杂度为$O((n+m)\log {maxd})$。
注意在预处理时求出需要使用的lca和路径长度，本题我使用了倍增lca，但是用tarjan显然会更优，本题写倍增常数偏大，需要卡常。
#include<cstdio>
#include<cstring>
using namespace std;
inline void swap(int &x,int &y){int p=x;x=y;y=p;}
inline int max(int a,int b){return a>b?a:b;}
inline int isdigit(char c){return c>='0'&&c<='9';}
inline int read(){
register int ch,flag=0,rs;
while(!isdigit(ch=getchar()))(ch=='-')&&(flag=1);
for(rs=ch-'0';isdigit(ch=getchar());rs=rs*10+ch-'0');
(flag)&&(rs=-rs);
return rs;
}
const int MAXN = 300001;
int n,m;
int hd[MAXN<<1],to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],cnt;
inline void add_edge(int u,int v,int w){to[++cnt]=v;nxt[cnt]=hd[u];val[cnt]=w;hd[u]=cnt;}
int dep[MAXN],dis[MAXN],fa[MAXN][30];
void tree(int u,int f){
dep[u]=dep[fa[u][0]=f]+1;
for(register int i=0;fa[u][i];++i)fa[u][i+1]=fa[fa[u][i]][i];
for(register int i=hd[u];i;i=nxt[i])
if(to[i]!=f){
dis[to[i]]=dis[u]+val[i];
tree(to[i],u);
}
}
inline int lca(int u,int v){
if(dep[u]>dep[v])swap(u,v);
for(register int i=20;i>=0;--i)if(dep[v]-(1<<i)>=dep[u])v=fa[v][i];
if(u==v)return u;
for(register int i=20;i>=0;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int dlt[MAXN],num,maxp;
inline void reset(){memset(dlt,0,sizeof(int)*(n+1));num=maxp=0;}
void getans(int u){
for(register int i=hd[u];i;i=nxt[i]){
if(to[i]==fa[u][0])continue;
getans(to[i]);
dlt[u]+=dlt[to[i]];
}
if(dlt[u]==num)maxp=max(maxp,dis[u]-dis[fa[u][0]]);
}
struct Route{
int u,v,lca,dis;
}route[MAXN];
int maxd;
inline int check(int x){
reset();
for(register int i=1;i<=m;++i){
if(route[i].dis>x){
++num;
++dlt[route[i].u],++dlt[route[i].v];
dlt[route[i].lca]-=2;
}
}
if(!num)return 1;
getans(1);
if(maxd-maxp>x)return 0;
return 1;
}
int main(){
//freopen("test.txt","r",stdin);
n=read();m=read();
for(register int i=1,u,v,w;i<n;++i){
u=read();v=read();w=read();
add_edge(u,v,w);add_edge(v,u,w);
}
tree(1,0);
for(register int i=1;i<=m;++i){
route[i].u=read();route[i].v=read();
route[i].lca=lca(route[i].u,route[i].v);
route[i].dis=dis[route[i].u]+dis[route[i].v]-(dis[route[i].lca]<<1);
maxd=max(maxd,route[i].dis);
}
int l=0,r=maxd,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}版权声明：本文是原创文章，版权归 无限UCW 所有。
本文链接：https://ucw.moe/archives/solution-luogu-p2680.html
本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。
