题目大意
这还不是人尽皆知?
有一棵树, 每个节点放军队的代价是\(a_i\), 一条边连接的两个点至少有一个要放军队, 还有\(q\)次询问, 每次规定其中的两个一定需要/不可放置军队, 问这样修改以后的最小代价.
解题思路
考虑一个朴素的DP, 设\(f_{x,0/1}\)表示这个点选/不选的最小代价. 显然有
\[f_{x,0}=\sum f_{y,1}
\]
\[f_{x,1}=a_x+\sum \min(f_{y,0}, f_{y,1})
\]
其中\(y\)是\(x\)的儿子. 最后的答案显然是\(min(f_{1,0}, f_{1,1})\)(1是根)
注意到我们每一次修改以后, 影响到的是从这个点到根节点的一条链. 我们需要快速修改这一段的\(f\)值. 怎么样可以使这个操作的时间复杂度变得正确一点呢? 显然树剖吧.
那就剖咯. 对轻重儿子区别对待. 设\(g_{x,0/1}\)表示\(x\)这个点选/不选, 除了重儿子外的最小代价. 显然有
\[g_{x,0}=\sum_{y \ne son_x} f_{y,1}
\]
\[g_{x,1}=a_x+\sum_{y \ne son_x} \min(f_{y,0}, f_{y,1})
\]
只不过是少了一个重儿子而已
那么\(f\)可以借助\(g\)转移过来.
\[f_{x,0}=f_{son,1}+g_{x,0}
\]
\[f_{x,1}=\min(f_{son,0}, f_{son,1})+g_{x,1}
\]
问题来了. 怎么维护一条链的信息?
考虑重新定义矩阵乘法, 若\(AB=C\), 则
\[C_{i,j}=\min_{k}(A_{i,k}+B_{k,j})
\]
于是转移方程可以写成如下
\[\begin{bmatrix}
+\infty & g_{x,0}\\
g_{x,1} & g_{x,1}
\end{bmatrix}
\begin{bmatrix}
f_{son,0}\\
f_{son,1}
\end{bmatrix}
=
\begin{bmatrix}
f_{x,0} \\
f_{x,1}
\end{bmatrix}
\]
在每一条链上维护\(g\)所在矩阵的乘积. 把一个询问按照重链分解成几条从当前点到根节点的链即可. 考虑当我们限制一个点强制选/不选后, 只需要把\(g\)数组对应的值赋成\(+\infty\)即可.
后记
其实一次有两个被限制了, 就是在暗示我们除了动态DP还有更简单的联赛做法.
但是我太懒了, 而且没做过树链剖分的题, 所以试一下(没错蒟蒻的第一个树链剖分就是做动态DP)
(可能是本人写过最长的Code?)
#include <cstdio>
#include <cstring>
#define N 100010
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3fll
#define init(a, b) memset(a, b, sizeof(a))
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(int i = (a); i >= (b); --i)
//#pragma GCC optimize(2)
using namespace std;
inline int read() // notice : 1. long long ? 2. negative ?
{
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
inline ll min(ll a, ll b){return a < b ? a : b;}
struct Matrix
{
ll a[2][2];
inline Matrix(){init(a, 0x3f);}
inline Matrix(int){a[0][0] = a[1][1] = 0; a[0][1] = a[1][0] = INF;}
inline Matrix(ll g0, ll g1){a[0][0] = INF, a[0][1] = g0, a[1][0] = a[1][1] = g1;}
inline Matrix operator*(const Matrix &b)
{
Matrix ret;
fo(i, 0, 1) fo(j, 0, 1) fo(k, 0, 1) ret.a[i][j] = min(ret.a[i][j], a[i][k] + b.a[k][j]);
return ret;
}
}tr[N << 2];
int n, q, ls[N << 2], rs[N << 2], rt[N], top[N], fa[N], sz[N], son[N], dfn[N], end[N], a[N], to[N << 1], pre[N << 1], last[N];
ll f[N][2], g[N][2];
#define mid ((l + r) >> 1)
void build(int &t, int l, int r)
{
static int tot = 0;
!t && (t = ++tot);
if(l == r) return ;
build(ls[t], l, mid); build(rs[t], mid + 1, r);
}
void insert(int t, int l, int r, Matrix v, int w)
{
if(l == r) return (void)(tr[t] = v, 0);
w <= mid ? insert(ls[t], l, mid, v, w) : insert(rs[t], mid + 1, r, v, w);
tr[t] = tr[ls[t]] * tr[rs[t]];
}
Matrix query(int t, int l, int r, int fl, int fr)
{
if(fl <= l && r <= fr) return tr[t];
Matrix ret(1);
fl <= mid && (ret = ret * query(ls[t], l, mid, fl, fr), 1);
fr > mid && (ret = ret * query(rs[t], mid + 1, r, fl, fr), 1);
return ret;
}
inline void add(int u, int v){static int tot = 0; to[++tot] = v, pre[tot] = last[u], last[u] = tot;}
inline void dfs1(int u)
{
sz[u] = 1, f[u][1] = a[u];
for(int i = last[u]; i; i = pre[i])
if(to[i] ^ fa[u])
{
int v = to[i];
fa[v] = u; dfs1(v), sz[u] += sz[v];
f[u][0] += f[v][1], f[u][1] += min(f[v][0], f[v][1]);
sz[v] > sz[son[u]] && (son[u] = v);
}
}
inline void dfs2(int u)
{
static int tot = 0;
dfn[u] = ++tot, g[u][1] = a[u];
if(son[u]) top[son[u]] = top[u], dfs2(son[u]), end[u] = end[son[u]];
else end[u] = u;
for(int i = last[u]; i; i = pre[i])
if(to[i] ^ fa[u] && to[i] ^ son[u])
{
int v = to[i];
top[v] = v;
g[u][0] += f[v][1], g[u][1] += min(f[v][0], f[v][1]);
dfs2(v);
}
}
inline void update(int x)
{
for(; x; x = fa[x])
{
insert(rt[top[x]], dfn[top[x]], dfn[end[x]], Matrix(g[x][0], g[x][1]), dfn[x]);
Matrix p = tr[rt[x = top[x]]];
// printf("f[%d] : %lld %lld\n", x, f[x][0], f[x][1]);
g[fa[x]][0] -= f[x][1], g[fa[x]][1] -= min(f[x][0], f[x][1]);
f[x][0] = min(p.a[0][0], p.a[0][1]), f[x][1] = min(p.a[1][0], p.a[1][1]);
g[fa[x]][0] += f[x][1], g[fa[x]][1] += min(f[x][0], f[x][1]);
}
}
int main()
{
freopen("defense.in", "r", stdin);
freopen("defense.out", "w", stdout);
n = read(), q = read(); scanf(" %*s");
fo(i, 1, n) a[i] = read();
int u, v, x, y; ll t1, t2;
fo(i, 2, n) u = read(), v = read(), add(u, v), add(v, u);
top[1] = 1;
dfs1(1);
dfs2(1);
fo(i, 1, n) if(top[i] == i) build(rt[i], dfn[i], dfn[end[i]]);
fo(i, 1, n) insert(rt[top[i]], dfn[top[i]], dfn[end[i]], Matrix(g[i][0], g[i][1]), dfn[i]);
fo(i, 1, q)
{
u = read(), x = read() ^ 1, v = read(), y = read() ^ 1;
t1 = g[u][x], t2 = g[v][y];
g[u][x] = INF, update(u), g[v][y] = INF, update(v);
ll ans = min(f[1][0], f[1][1]);
printf("%lld\n", ans < INF ? ans : -1);
g[u][x] = t1, update(u), g[v][y] = t2, update(v);
}
return 0;
}