电子商务网站进度的基本流程,免费网站软件,南宁建网站,wordpress手机怎么分享链接F. Roads in the Kingdom(树形dp) 题意#xff1a; 给一张n个点n条边的无向带权图 定义不便利度为所有点对最短距离中的最大值 求出删一条边之后#xff0c;保证图还连通时不便利度的最小值 $n 2e5 $\(w_i 1e9\) 思路:树形dp 这个图是一个环上挂着很多颗树#xf…F. Roads in the Kingdom(树形dp) 题意 给一张n个点n条边的无向带权图 定义不便利度为所有点对最短距离中的最大值 求出删一条边之后保证图还连通时不便利度的最小值 $n 2e5 $\(w_i 1e9\) 思路:树形dp 这个图是一个环上挂着很多颗树首先把这个环处理出来 删边只能在环上进行所以可以先求出以环上每个点为根的树的直径和最大深度dep 答案来源分为二种 树内部两点最远距离 - 直径 (树形dp 或者 两次bfs)两棵树深度最大的两点配对 假设环长度为\(k\),把环变成一个序列\(a_1,a_2,...,a_k\) 令\(a_0 a_k\) 选择\(a_0\)做起点用\(s_i\)表示第\(i\)个点到起点的距离 考虑每次断开的边为\(e(a_{i-1},a_i)\),那么答案分为三种情况 序列\(1\)到\(i-1\)中选两个点配对取最大值序列\(i\)到\(k\)中选两个点配对取最大值前后各取一个点配对取最大值 计算第一种情况 假设取的两个点为\(1xyi-1\), 则距离\(d dep[x] dep[y] dis[x][y] dep[x] - s[x] dep[y] s[y]\) 这样我们只需要顺序枚举维护\(dep[x] - s[x]\)的最大值即可 同理第二种情况只需要逆序枚举维护\(dep[x] s[x]\)的最大值即可 考虑第三种情况 假设取的点为\(1 x i - 1 , i y k\) 则距离\(d dep[x] dep[y] dis[x][y] dep[x] dep[y] s[k] - (s[y] - s[x])\) $d (dep[x] s[k] s[x]) (dep[y] - s[y]) $ 同理顺序可算出第一部分最大值逆序可以算出第二部分最大值 最后在删边后三种情况的最大值里取最小值再和树内部直径比较即可 #includebits/stdc.h
#define LL long long
#define P pairint,int
#define ls(i) seg[i].lc
#define rs(i) seg[i].rc
using namespace std;
const int N 2e5 10;
const LL inf 1e18;
int read(){int x 0;char c getchar();while(c 0 || c 9) c getchar();while(c 0 c 9) x x * 10 c - 48, c getchar();return x;
}
vectorPG[N];
int n,k;
int a[N],pa[N],e[N];
LL s[N],dep[N],ans;
void dfs(int u,int fa){pa[u] fa;for(auto v:G[u]){if(v.first fa) continue;if(pa[v.first] 0) {e[v.first] v.second;dfs(v.first,u);}else if(!k){int x u;a[0] v.first,s[1] v.second;while(x ! v.first) {a[k] x,s[k1] s[k] e[x],x pa[x];}a[k] v.first;}}
}
void dp(int u){pa[u] 0;for(auto v:G[u]){if(pa[v.first] ! 0){dp(v.first);ans max(ans,dep[v.first] v.second dep[u]);dep[u] max(dep[u], dep[v.first] v.second);}}
}
LL sL[N],sR[N],L[N],R[N];///把环变成序列断开的边左边配对右边配对左右配对的最大值
int main(){int u,v,w;n read();for(int i 1;i n;i){u read(),v read(),w read();G[u].push_back(P(v,w));G[v].push_back(P(u,w));}k 0;ans 0;dfs(1,-1);for(int i 1;i k;i) pa[a[i]] 0;for(int i 1;i k;i) dp(a[i]);LL mx -inf;L[0] sL[0] -inf;for(int i 1;i k;i){sL[i] max(sL[i-1],dep[a[i]] s[i] mx);L[i] max(L[i-1],dep[a[i]] s[k] s[i]);mx max(mx, dep[a[i]] - s[i]);}sR[k1] R[k1] mx -inf;for(int i k;i 1;i--){sR[i] max(sR[i1],dep[a[i]] - s[i] mx);R[i] max(R[i1],dep[a[i]] - s[i]);mx max(mx, dep[a[i]] s[i]);}LL tmp inf;for(int i 1;i k;i) tmp min(tmp,max(L[i-1]R[i],max(sL[i-1],sR[i])));coutmax(ans,tmp)endl;return 0;
} 转载于:https://www.cnblogs.com/jiachinzhao/p/7305578.html
