题目传送门
想抄一个短一点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;
}