题目链接 https://www.luogu.org/problem/P2680
震惊 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;
- View Code
短短几行但是非常有用, 然后我们再求出该答案与超出的那个边权的差的最大值. 之后更新所有点的差分数组, 因为树上两点间路径唯一, 所以要想从某个点过, 必须先从它 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\n",ljb);
- return 0;
- }
- View Code
好题.
来源: http://www.bubuko.com/infodetail-3158955.html