题目传送门
想抄一个短一点ddp板子。然后照着Jode抄,莫名其妙多了90行和1.3k。
Code
/** * loj * Problem#2955 * Accepted * Time: 2653ms * Memory: 25616k */ #include <bits/stdc++.h> using namespace std; typedef bool boolean; const int N = 1e5 + 5; #define ll long long template <typename T> T smin(T a, T b) { return min(a, b); } template <typename T, typename ...Q> T smin(T a, const Q &...args) { return min(a, smin(args...)); } const ll llf = 1e12; typedef class Data { public: ll a[2][2]; Data() { } Data(ll x) { a[0][0] = llf, a[0][1] = 0; a[1][0] = x, a[1][1] = x; } Data(ll x, ll y, ll z, ll w) { a[0][0] = x, a[0][1] = y; a[1][0] = z, a[1][1] = w; } Data get() { ll g = min(a[0][0], a[0][1]); ll f = min(a[1][0], a[1][1]); g = min(g, f); return Data(f, f, g, g); } ll* operator [] (int p) { return a[p]; } friend Data operator * (Data a, Data b) { Data rt; rt[0][0] = min(a[0][0] + b[0][0], a[0][1] + b[1][0]); rt[0][1] = min(a[0][0] + b[0][1], a[0][1] + b[1][1]); rt[1][0] = min(a[1][0] + b[0][0], a[1][1] + b[1][0]); rt[1][1] = min(a[1][0] + b[0][1], a[1][1] + b[1][1]); return rt; } friend Data operator + (Data a, Data b) { Data rt; rt[0][0] = a[0][0] + b[0][0]; rt[0][1] = a[0][1] + b[0][1]; rt[1][0] = a[1][0] + b[1][0]; rt[1][1] = a[1][1] + b[1][1]; return rt; } friend Data operator - (Data a, Data b) { Data rt; rt[0][0] = a[0][0] - b[0][0]; rt[0][1] = a[0][1] - b[0][1]; rt[1][0] = a[1][0] - b[1][0]; rt[1][1] = a[1][1] - b[1][1]; return rt; } ll get_ans() { ll rt = smin(a[0][0], a[0][1], a[1][0], a[1][1]); return (rt >= llf) ? (-1) : (rt); } } Data; typedef class SegTreeNode { public: Data d; SegTreeNode *fa; SegTreeNode *l, *r; void push_up() { d = l->d * r->d; } } SegTreeNode; typedef class Chain { public: SegTreeNode *st; int len, top; Chain() { } Chain(int top); void update(int, Data, Data); } Chain; SegTreeNode pool[N << 1]; SegTreeNode *_top = pool; int S[N]; Data dat[N]; int tp; Chain *ch[N]; SegTreeNode *tr[N]; void build(SegTreeNode*& p, int l, int r) { p = _top++; if (l == r) { p->d = dat[S[l]]; tr[S[l]] = p; return; } int mid = (l + r) >> 1; build(p->l, l, mid); build(p->r, mid + 1, r); p->push_up(); p->l->fa = p; p->r->fa = p; } Chain::Chain(int top) : st(_top), len(tp), top(top) { reverse(S + 1, S + tp + 1); build(st, 1, len); for (int i = 1; i <= len; i++) { ch[S[i]] = this; } if (top) { dat[top] = dat[top] + st->d.get(); } } void Chain::update(int x, Data old_d, Data new_d) { Data nold_d = st->d.get(); tr[x]->d = tr[x]->d - old_d + new_d; for (SegTreeNode *p = tr[x]->fa; p; p = p->fa) p->push_up(); if (top) { ch[top]->update(top, nold_d, st->d.get()); } } int n, m; int p[N]; int sz[N], zson[N]; vector<int> G[N]; void dfs1(int p, int fa) { int mx = 0, &id = zson[p]; sz[p] = 1; for (auto e : G[p]) { if (e ^ fa) { dfs1(e, p); sz[p] += sz[e]; if (mx < sz[e]) { mx = sz[e]; id = e; } } } } void dfs2(int p, int fa) { if (zson[p]) { for (auto e : G[p]) { if ((e ^ fa) && (e ^ zson[p])) { dfs2(e, p); new Chain(p); } } dfs2(zson[p], p); } else { tp = 0; } S[++tp] = p; } int main() { freopen("defense.in", "r", stdin); freopen("defense.out", "w", stdout); scanf("%d%d%*s", &n, &m); for (int i = 1, x; i <= n; i++) { scanf("%d", &x); dat[i] = x; p[i] = x; } for (int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs1(1, 0); dfs2(1, 0); new Chain(0); int a, x, b, y; while (m--) { scanf("%d%d%d%d", &a, &x, &b, &y); Data olda = p[a], oldb = p[b]; Data na = Data(llf * (1 - x)), nb = Data(llf * (1 - y)); ch[a]->update(a, olda, na); ch[b]->update(b, oldb, nb); ll ans = ch[1]->st->d.get_ans() + olda[1][0] * x + oldb[1][0] * y; ch[a]->update(a, na, olda); ch[b]->update(b, nb, oldb); printf("%lld\n", ans); } return 0; }