JZOJ6232 【NOI2019模拟2019.6.25】喜欢最最痛（凸函数，贪心，动态dp）

Description：

神树大人种了一棵有边权的树，由于这是神树大人种的树，所以这棵树被命名为神
神树。神神树的边权为正. 整. 数. 。神树大人命令龚诗锋从 1 号点开始走一个路径并最终
回到1 号点，且这条路径经过了所有的边。一条路径的代价就是它经过的边的边权之
和。龚诗锋可以加若干条额外边，第 i 条加的额外边的边权为正. 整. 数. Ai。注. 意. ，龚. 诗. 锋.
不. 一. 定. 要. 经. 过. 所. 有. 的. 额. 外. 边. 。
由于龚诗锋喜欢最最痛，所以对于所有的K ∈[0;m]，你需要输出允许加<= K 条额
外边的最小路径代价。
1<=n<=1e5,5s

题解：

不难想到假设求出了$f[i]$表示$i$条不相交路径的最大长度和，那么对一个K，就需要求出l，使$2\ast 边权和-f[i]+前K条边中前l小的和$的最小值

当然这个可以暴力用个平衡树（离线线段树）二分。

注意到$f$是个凸函数，然后前l小的和也是个凸函数，且随着K的增大，l只会右移，所以可以用两个multiset维护，一个存选了的l条边，另一个存没选的，细节比较简单不讲了。

那么问题在于求f，可以暴力对拍，复杂度 O ( n 2 ) O(n^2) O(n2)

然后这个东西是优化不了的，考虑一个贪心，每次选直径，把直径边权取反，继续找直径。

显然我是不会证明这个东西的正确性的，但是至少能找到i条不相交的路径。

那么这个东西显然可以用ddp优化，update细节有点多，还需要用一个multiset维护一个点的虚儿子的最小和次小，access要改改写法。

重载一堆东西以后还是可以写的hhh

复杂度 O ( n l o g 2 n ) O(n~log^2n) O(n log2n)，常数巨大

Code：

#include
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;int by;const int N = 2e5 + 5;int n, m, x, y, z, w[N];
int v[N];struct P {int x, y; ll z;P(){}P(int _x, int _y, ll _z) { x = _x, y = _y, z = _z;}
};
bool operator <(P a, P b) {if(a.z < b.z) return 1;if(a.z > b.z) return 0;if(a.x < b.x) return 1;if(a.x > b.x) return 0;return a.y < b.y;
}
P operator +(P a, P b) { return P(!a.x ? b.x : a.x, !b.y ? a.y : b.y, a.z + b.z);}P fan(P a) { swap(a.x, a.y); return a;}struct nod {P f1, f2, g, v;
};nod a[N][2][2];
multiset<P> s[N], g[N];
int fa[N], t[N][2], rev[N], rf[N], dd[N], pf[N];
#define i0 t[i][0]
#define i1 t[i][1]P calc1(multiset<P> &s) {if(!s.size()) return P(0, 0, 0);return *s.rbegin();
}
P calc2(multiset<P> &s) {if(s.size() < 2) return P(0, 0, 0);return (*++s.rbegin());
}
template<class T> void cmax(T &a, T b) {if(a < b) a = b;} 
void upd(int i, multiset<P> &s, multiset<P> &g, int V, nod &a, nod b, nod c) {P w = P(i, i, V);a.f1 = b.f1; cmax(a.f1, b.v + w + c.f1); cmax(a.f1, b.v + w + calc1(s));a.f2 = c.f2; cmax(a.f2, b.f2 + w + c.v); cmax(a.f2, fan(calc1(s)) + w + c.v);a.g = max(b.g, c.g);if(g.size()) cmax(a.g, *g.rbegin());cmax(a.g, b.f2 + w + c.f1);cmax(a.g, fan(calc1(s)) + w + calc2(s));cmax(a.g, b.f2 + w + calc1(s));cmax(a.g, fan(calc1(s)) + w + c.f1);a.v = b.v + w + c.v;
}
void upd(int i) {upd(i, s[i], g[i], v[i], a[i][0][0], a[i0][0][0], a[i1][0][0]);upd(i, s[i], g[i], v[i], a[i][1][0], a[i1][1][0], a[i0][1][0]);upd(i, s[i], g[i], -v[i], a[i][0][1], a[i0][0][1], a[i1][0][1]);upd(i, s[i], g[i], -v[i], a[i][1][1], a[i1][1][1], a[i0][1][1]);
}
void fan(int i) {if(i) {swap(i0, i1);swap(a[i][0][0], a[i][1][0]);swap(a[i][0][1], a[i][1][1]);rev[i] ^= 1;}
}
void fu(int i) {if(i) {v[i] = -v[i];swap(a[i][0][0], a[i][0][1]);swap(a[i][1][0], a[i][1][1]);rf[i] ^= 1;}
}
void down(int i) {if(rev[i]) fan(i0), fan(i1), rev[i] = 0;if(rf[i]) fu(i0), fu(i1), rf[i] = 0;
}
void xc(int x) {for(; x; x = fa[x]) dd[++ dd[0]] = x;while(dd[0]) down(dd[dd[0] --]);
}
int lr(int x) { return t[fa[x]][1] == x;}
void rotate(int x) {int y = fa[x], k = lr(x);t[y][k] = t[x][!k]; if(t[x][!k]) fa[t[x][!k]] = y;fa[x] = fa[y]; if(fa[y]) t[fa[y]][lr(y)] = x;fa[y] = x; t[x][!k] = y; pf[x] = pf[y];upd(y); upd(x);
}
void splay(int x, int y) {xc(x);for(; fa[x] != y; rotate(x))if(fa[fa[x]] != y) rotate(lr(x) == lr(fa[x]) ? fa[x] : x);
}
void access(int x) {int xx = x;for(int y = 0; x; ) {splay(x, 0);if(y) {s[x].erase(s[x].find(a[y][0][0].f1));g[x].erase(g[x].find(a[y][0][0].g));}y = x, x = pf[x];}x = xx;for(int y = 0; x; ) {splay(x, 0); fa[t[x][1]] = 0, pf[t[x][1]] = x;if(t[x][1]) {s[x].insert(a[t[x][1]][0][0].f1);g[x].insert(a[t[x][1]][0][0].g);}t[x][1] = y, fa[y] = x, pf[y] = 0;y = x, upd(x), x = pf[x];}
}
void mr(int x) {access(x); splay(x, 0);fan(x);
}
void link(int x, int y) {mr(x); mr(y);pf[x] = y;s[y].insert(a[x][0][0].f1);g[y].insert(a[x][0][0].g);access(x);
}ll f[N];ll sum, ans;
multiset<int> s1, s2;int main() {freopen("love.in", "r", stdin);freopen("love.out", "w", stdout);scanf("%d %d", &n, &m);fo(i, 1, n - 1) {scanf("%d %d %d", &x, &y, &z);ans += z * 2;v[n + i] = z;link(x, n + i); link(n + i, y);}fo(i, 1, n) {mr(1);P p = a[1][0][0].g;f[i] = f[i - 1];if(p.z >= 0) {f[i] += p.z;mr(p.x); access(p.y); splay(p.y, 0);fu(p.y);}}pp("%lld ", ans);int l = 0;fo(i, 1, m) {scanf("%d", &w[i]);if(s1.size() && (*s1.rbegin()) > w[i]) {sum += w[i] - (*s1.rbegin());s2.insert(*s1.rbegin());s1.erase(s1.find(*s1.rbegin()));s1.insert(w[i]);} else s2.insert(w[i]);while(s2.size() && (sum + *s2.begin()) - f[l + 1] <= sum - f[l]) {sum += *s2.begin();s1.insert(*s2.begin());s2.erase(s2.begin());l ++;}pp("%lld ", ans + sum - f[l]);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！