泉州洛江住房和城乡建设局网站,ASP.NET2.0网站开发全程解析,大学社团网站建设,微信商城小程序官网传送门 文章目录题目描述解析问题代码题目描述 解析
求最大值的最小值 容易想到二分 然后。。。就没有然后了。。。 看了题解 学会了一个新技能#xff1a;树上差分 #xff08;其实学长之前好像讲过。。。#xff09;
一般的#xff0c;对于一条A到B的路径#xff0c;如…传送门
文章目录题目描述解析问题代码题目描述 解析
求最大值的最小值 容易想到二分 然后。。。就没有然后了。。。 看了题解 学会了一个新技能树上差分 其实学长之前好像讲过。。。
一般的对于一条A到B的路径如果要将其全部加上一个值w。我们可以把AB两点的前缀加w再把它们的lca及lca的父亲减去w最后统计时用dfs统计每个点的价值就是其本身及子树的前缀值之和 画个图就能很直观的看出来请读者自行动笔探究~~绝对不是我懒~~ lca可以用许多算法优化到log这样时间复杂度就很优秀啦
本题对于一个二分出来的值mid如果有一些路径的长度大于mid那么删的边一定是这些不符合的路径的公共边不然它还是不符合 就相当与每次把不符合的路径上的点全部加1再统计点权恰好等于不符合路径个数的点它们之间的边就是可以删的边这就能用差分啦 其中选一条最大的看减完它行不行即可
问题
本题到这里思路就结束了 但真正做起来真的有点搬砖。。。 还遇到了很多细节问题 1.树上倍增的时候要注意单链时最后不用再跳一边father了 2.300000的log大于15我掰手指头当成30000了。。。调了好久 3.双向边要开二倍 这都是经常遇到的问题代码复杂起来就又忘了一定要引以为戒注意细节
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N3e5100;
int n,m;
struct node{int to,nxt,v;
}p[2*N];
int fi[N],cnt-1;
void addline(int x,int y,int v){p[cnt](node){y,fi[x],v};fi[x]cnt;
}int dep[N],fa[N],fv[N];
void dfs(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;fa[to]x;dep[to]dep[x]1;fv[to]p[i].v;dfs(to,x);}return;
}
int pl[22][N],dis[22][N],mi[22];
void solve(){mi[0]1;for(int i1;i20;i) mi[i]mi[i-1]*2;for(int i2;in;i){pl[0][i]fa[i];dis[0][i]fv[i];}for(int k1;k20;k){for(int i1;in;i){if(dep[i]mi[k]) continue;pl[k][i]pl[k-1][pl[k-1][i]];dis[k][i]dis[k-1][i]dis[k-1][pl[k-1][i]];}}return;
}
int place,tot;
void find(int x,int y){tot0;if(dep[x]dep[y]) swap(x,y);for(int k20;k0;k--){if(dep[x]-mi[k]dep[y]){totdis[k][x];xpl[k][x];}}for(int k20;k0;k--){if(dep[x]mi[k]||pl[k][x]pl[k][y]) continue;totdis[k][x];xpl[k][x];totdis[k][y];ypl[k][y];
// printf(x%d y%d tot%d\n,x,y,tot);}placex;if(x!y){totfv[x];totfv[y];placefa[place];}
}struct node2{int x,y,len,lca;
}q[N];
int a,b,c;int num;
int pre[N],sum[N];
void dfs2(int x,int f,int ans){sum[x]pre[x];for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs2(to,x,ans);sum[x]sum[to];}if(sum[x]!num) return;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(sum[to]num){ansmax(ans,p[i].v);
// printf(x%d y%d v%d\n,x,to,fv[to]);}}return;
}
bool check(int mid){int mx0;num0;memset(pre,0,sizeof(pre));memset(sum,0,sizeof(sum));
// printf(check: (%d)\n,mid);for(int i1;im;i){if(q[i].lenmid){num;mxmax(mx,q[i].len);pre[q[i].x];pre[q[i].y];pre[q[i].lca]--;pre[fa[q[i].lca]]--;}}if(num0) return true;int ans0;dfs2(1,0,ans);
// printf( num%d ans%d\n,num,ans);if(mx-ansmid) return true;else return false;
}
int main(){memset(fi,-1,sizeof(fi));
// printf(%d,sizeof(pl)/1024/1024);scanf(%d%d,n,m);for(int i1;in;i){scanf(%d%d%d,a,b,c);addline(a,b,c);addline(b,a,c);}dfs(1,0);solve();
// for(int i1;in;i) printf(i%d fa%d dep%d\n,i,fa[i],dep[i]);for(int i1;im;i){scanf(%d%d,a,b);find(a,b);q[i](node2){a,b,tot,place};
// printf(tot%d pl%d\n,tot,place);}int st0,ed2e9;while(sted){
// printf(st%d ed%d\n,st,ed);int mid(sted)1;if(check(mid)) edmid;else stmid1;}printf(%d,st);
}
/*
12 3
1 2 8
1 3 1
1 4 8
2 5 6
2 7 5
2 6 4
6 8 7
6 9 5
3 10 6
3 12 3
10 11 5
1 11
3 11
10 116 4
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
2 4
*/
