震惊noip被ccf暂停了，不过多半是改个名字什么的。noip的好题还是可以做一做的，这道题的确值得一做，我们看他题上说的是最短的时间是所有经过边权和的最大值决定，也就是说最大值最小，显然的二分答案。由于题目中的关系是一棵树或一条链，所以就可以往这方面想想，可是我就想不到。先打个暴力三十分，针对那些m等于1的情况，直接求出两点间的最短路再减去最短路径上的最长边就可以了。spfa复杂度O（玄学），堆优化dijkstra是O（nlogn），30分就到手了。不过要打正解还是挺不容易的，还是去看看题解是怎么说的，大多数的题解都提到了树上差分这个玩意儿。那我们还是考虑一下，先用树剖求LCA，预处理出询问的点两两之间的距离，然后二分check+树上差分，check就check最大值最小。
关键步骤便是这个树上差分，推荐此博客
我们一旦发现一个路径大于我们的答案，就把该路径的两个端点记录下来有多少次经过，也就是树上差分。
cha[q[i].fro]++; cha[q[i].to]++; cha[q[i].lca]-=2;
短短几行但是非常有用，然后我们再求出该答案与超出的那个边权的差的最大值。之后更新所有点的差分数组，因为树上两点间路径唯一，所以要想从某个点过，必须先从它father身上过。所以他的差分值累加到father上。
最后便是判断，如果有某个点被经过的次数恰好是不合法边的数量，边权比最大差值大或等于，就是一个可行解，就将该点的边改为虫洞即可。
还要记住每次二分答案的时候，差分数组要清空，从头再来。最终复杂度O（nlogn）。
完整的代码如下
#include<bits/stdc++.h> using namespace std; const int maxn=3e6+7; int dep[maxn],son[maxn],size[maxn],w[maxn],fa[maxn],dis[maxn],hash[maxn]; int top[maxn],id[maxn],rev[maxn],Time; int cha[maxn]; struct node{ int nxt,to,val; }edge[maxn*3]; struct node1{ int fro,to,lca,diss; }q[maxn*4]; int head[maxn],cnt; int n,m,x,y,v,qx,qy; int sum,l,r; void add(int x,int y,int v){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=v; head[x]=cnt; } void dfs1(int x,int f){ fa[x]=f; dep[x]=dep[f]+1; size[x]=1; int maxson=-1; for(int i=head[x];i;i=edge[i].nxt){ int go=edge[i].to; if(go==fa[x]) continue; dis[go]=dis[x]+edge[i].val; dfs1(go,x); size[x]+=size[go]; if(size[go]>maxson){ maxson=size[go]; son[x]=go; } } } void dfs2(int x,int topf){ top[x]=topf; if(!son[x]) return; dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nxt){ int go=edge[i].to; if(go==son[x]||go==fa[x]) continue; dfs2(go,go); } } int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } //--------------------------------以上是树剖求LCA部分 void dfs3(int x){ for(int i=head[x];i;i=edge[i].nxt){ int go=edge[i].to; if(go==fa[x]) continue; dfs3(go); cha[x]+=cha[go]; } } void dfs4(int x){ for(int i=head[x];i;i=edge[i].nxt){ int go=edge[i].to; if(go==fa[x]) continue; hash[go]=i;//记录下出边的序号 dfs4(go); } } bool check(int x){ int cnt=0,ans=0; memset(cha,0,sizeof(cha)); for(int i=1;i<=m;i++){ if(q[i].diss>x){//如果有一条路径不符合 cha[q[i].fro]++;//记录下，相当于是树上差分每点权值+1 cha[q[i].to]++; cha[q[i].lca]-=2; cnt++; ans=max(ans,q[i].diss-x); //看最大的修改值 } } if(!cnt) return true;//没有不合法边，此答案可行 dfs3(1);//统计各点的差分次数 for(int i=1;i<=n;i++) if(cha[i]==cnt&&edge[hash[i]].val>=ans) return true; //如果有某个点是多个边的公共点，边权比最大差值大或等于，就是一个可行解 return false; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&v); add(x,y,v);add(y,x,v); } dfs1(1,0);dfs2(1,1);dfs4(1); for(int i=1;i<=m;i++){ scanf("%d%d",&qx,&qy); q[i].fro=qx; q[i].to=qy; q[i].lca=LCA(q[i].fro,q[i].to); q[i].diss=dis[q[i].fro]+dis[q[i].to]-2*dis[q[i].lca];//预处理出两点间路径 sum=max(sum,q[i].diss); } int ljb; l=0,r=sum; while(l<=r){//求最大值最小 int mid=(l+r)/2; if(check(mid)){ ljb=mid; r=mid-1; } else l=mid+1; } printf("%d ",ljb); return 0; }
好题。