題意簡述

給定一顆樹，每次操作可以使兩個(gè)點(diǎn)最短路上的點(diǎn)+1，求最大的點(diǎn)

題解思路

樹上差分

若操作u, v,則++f[u], ++f[v], --f[lca(u, v)], --f[father(lca(u, v))];

代碼

#include <cstdio> #include <algorithm> #define REG(i, u, op) for (register int i = h[u][op]; i; i = e[i][op].nxt) struct Edge {int to, nxt; }e[300000][2]; int n, k, u, v, ans; int cnt[2], h[100000][2]; int f[100000], fa[100000], ff[100000]; inline void add_edge(const int& u, const int& v, const bool& op) {e[++cnt[op]][op].to = v;e[cnt[op]][op].nxt = h[u][op];h[u][op] = cnt[op]; } int find(const int& x) {return fa[x] ^ x ? fa[x] = find(fa[x]) : x; } inline void add(const int& u, const int& v, const int& lca) {++f[u];++f[v];--f[lca];--f[ff[lca]]; } void dfs1(const int& x) {fa[x] = x;REG(i, x, 1) if (fa[e[i][1].to])add(e[i][1].to, x, find(e[i][1].to));REG(i, x, 0) if (!fa[e[i][0].to]){ff[e[i][0].to] = x;dfs1(e[i][0].to);fa[e[i][0].to] = x;} } int dfs2(const int& x) {int s = f[x];REG(i, x, 0) if (e[i][0].to ^ ff[x])s += dfs2(e[i][0].to);ans = std::max(ans, s);return s; } int main() {scanf("%d%d", &n, &k);for (register int i = 1; i < n; ++i){scanf("%d%d", &u, &v);add_edge(u, v, 0);add_edge(v, u, 0);}for (register int i = 1; i <= k; ++i){scanf("%d%d", &u, &v);add_edge(u, v, 1);add_edge(v, u, 1);}dfs1(1);dfs2(1);printf("%d\n", ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/xuyixuan/p/9696627.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P3128 [USACO15DEC]最大流Max Flow的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。