网站建设都需要什么文案,设计好的制作网站,口碑好网站建设资源,手机电脑网站设计题目链接 给定一棵树以及树上的 m m m 条通路#xff0c;我们可以在树上选取一条边#xff0c;将其权重置为 0 0 0#xff0c;目标是 min 将某条边权重置 0 max 通路权重 . \min_{将某条边权重置 0}\max 通路权重. 将某条边权重置0minmax通路权重.
20pts(m1)
当…题目链接 给定一棵树以及树上的 m m m 条通路我们可以在树上选取一条边将其权重置为 0 0 0目标是 min 将某条边权重置 0 max 通路权重 . \min_{将某条边权重置 0}\max 通路权重. 将某条边权重置0minmax通路权重.
20pts(m1)
当 m 1 m1 m1 时我们只需要求出树上的一条链上的权重和与权重最大值即可。
50pts
考虑一种暴力的算法枚举将哪一条边权重置 0 0 0然后重新在树上求解 m m m 条通路的权重。这个过程可以用 LCA 优化。任选一个结点为根预处理出每一条通路的两个端点的 LCA则路径长度可以通过树上差分快速计算。时间复杂度为 O ( n ( n m ) ) O(n(nm)) O(n(nm))。
80pts(树退化为链)
当树退化为链时这就是一个纯粹的数据结构问题。这类最小化最大值的问题可以考虑二分答案将其转化为判定问题。给定一个权重上界 w w w 后我们可以 O ( m ) O(m) O(m) 算出哪些通路的权重是超过这个上界的而这些通路全部位于一条链上因此我们可以 O ( m ) O(m) O(m) 求出它们的交集。然后在交集中找到权重最大的一条边如果将这条边的权重置 0 0 0 后所有通路的权重均不超过 w w w那么 w w w 就是一个可行的上界。
100pts
上面的二分答案方法给了我们初步的思路。现在只需考虑树上给定权重上界后如何判定首先任取一个结点作为根结点并将边权下推为点权。使用差分维护数组 f [ v ] f[v] f[v] 表示从 v v v 的父结点到 v v v 的这条边被经过了多少次。假设有 c n t cnt cnt 个权重超过上届的通路那么我们只要考虑被经过 c n t cnt cnt 次的边即可。代码如下
#includebits/stdc.h
using namespace std;const int maxn 3e5 10;struct edge
{int v, w;int nxt;
} e[maxn 1];
int n, m,
ver[maxn], w[maxn], a[maxn], b[maxn], c[maxn], d[maxn], f[maxn], s[maxn], num,
top[maxn], fa[maxn], size[maxn], son[maxn], dep[maxn], dis[maxn],
l, r, mid, ans, maxw;inline void adde(int u, int v, int w)
{static int ed 1;e[ed] (edge){ v, w, ver[u] };ver[u] ed;
}inline void dfs1(int u, int f)
{s[num] u;size[u] 1, fa[u] f;for(int i ver[u]; i; i e[i].nxt){int v e[i].v;if(size[v])continue;dep[v] dep[u] 1;w[v] e[i].w;dis[v] dis[u] w[v];dfs1(v, u);size[u] size[v];if(size[son[u]] size[v])son[u] v;}
}inline void dfs2(int u, int t)
{top[u] t;if(son[u])dfs2(son[u], t);for(int i ver[u]; i; i e[i].nxt){int v e[i].v;if(v fa[u] || v son[u])continue;dfs2(v, v);}
}inline int lca(int u, int v)
{while(top[u] ! top[v]){if(dep[top[u]] dep[top[v]])swap(u, v);u fa[top[u]];}return dep[u] dep[v] ? u : v;
}inline bool check(int k)
{memset(f, 0, sizeof f);int cnt 0;for(int i 1; i m; i){if(d[i] k)continue;f[a[i]], f[b[i]], f[c[i]] - 2;cnt;}for(int i n; i 1; i--){f[fa[s[i]]] f[s[i]];if(w[s[i]] maxw - k f[s[i]] cnt)return true;}return false;
}inline int read()
{static int x;static char c;x 0, c getchar();while(!isdigit(c))c getchar();while(isdigit(c))x (x 1) (x 3) (c ^ 48), c getchar();return x;
}int main()
{n read(), m read();for(int i 1; i n; i){int u read(), v read(), w read();adde(u, v, w);adde(v, u, w);l max(l, w);}dep[1] 1;dfs1(1, 0);dfs2(1, 1);for(int i 1; i m; i){a[i] read(), b[i] read();c[i] lca(a[i], b[i]);d[i] dis[a[i]] dis[b[i]] - (dis[c[i]] 1);r max(r, d[i]);}maxw r, l maxw - l, r;while(l r){mid (l r) 1;if(check(mid))ans mid, r mid - 1;elsel mid 1;}printf(%d, ans);return 0;
}
