题面
题解
对于每个节点，我们可以用树链剖分和线段树维护以下信息：
- 单独在某个点分配$i$个人的最大收益（可以$O(m)$计算）
- 分配$i$的最大收益（可以$O(m^2)$计算）
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::sort; using std::swap;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 20010, M = 51, T = 65600;
int n, m, q, X = 1 << 16, Y = ~0U >> 1, A, B, Q, op, x, y;
int fa[N], son[N], siz[N], top[N], dfn[N], dep[N], val[N], tim;
int cnt, from[N], to[N], nxt[N];
inline void addEdge(int u, int v) {
to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt;
}
struct P {
ll v[M];
P() { for(int i = 0; i < M; ++i) v[i] = 0; }
P operator + (P b) {
P c;
for(int i = 0; i < M; ++i) c.v[i] = max(v[i], b.v[i]);
return c;
}
P operator * (P b) {
P c;
for(int i = 0; i < M; ++i)
for(int j = 0; j < M - i; ++j)
c.v[i + j] = max(c.v[i + j], v[i] + b.v[j]);
return c;
}
}tmp, a[N], v0[T], v1[T], s0, s1;
//读入数据
inline int getint() {
A = ((A ^ B) + B / X + B * X) & Y;
B = ((A ^ B) + A / X + A * X) & Y;
return (A ^ B) % Q;
}
inline void gettmp() {
for(int i = 1; i <= m; ++i) tmp.v[i] = getint();
sort(&tmp.v[1], &tmp.v[m + 1]);
}
//线段树
inline void pushup(int o, int lc, int rc) { v0[o] = v0[lc] + v0[rc], v1[o] = v1[lc] * v1[rc]; }
void build(int o = 1, int l = 1, int r = n) {
if(l == r) { v0[o] = v1[o] = a[val[l]]; return ; }
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
build(lc, l, mid), build(rc, mid + 1, r), pushup(o, lc, rc);
}
void modify(int k, int o = 1, int l = 1, int r = n) {
if(l == r) { v0[o] = v1[o] = tmp; return ; }
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
if(k <= mid) modify(k, lc, l, mid);
else modify(k, rc, mid + 1, r);
pushup(o, lc, rc);
}
void query0(int ql, int qr, int o = 1, int l = 1, int r = n) {
if(l >= ql && r <= qr) { s0 = s0 + v0[o]; return ; }
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
if(ql <= mid) query0(ql, qr, lc, l, mid);
if(qr > mid) query0(ql, qr, rc, mid + 1, r);
}
void query1(int ql, int qr, int o = 1, int l = 1, int r = n) {
if(l >= ql && r <= qr) { s1 = s1 * v1[o]; return ; }
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
if(ql <= mid) query1(ql, qr, lc, l, mid);
if(qr > mid) query1(ql, qr, rc, mid + 1, r);
}
//树链剖分
void dfs(int u) {
siz[u] = 1, dep[u] = dep[fa[u]] + 1;
for(int i = from[u]; i; i = nxt[i]) {
int v = to[i]; dfs(v), siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs(int u, int t) {
dfn[u] = ++tim, val[tim] = u, top[u] = t;
if(!son[u]) return ; dfs(son[u], t);
for(int i = from[u]; i; i = nxt[i])
if(to[i] != son[u]) dfs(to[i], to[i]);
}
inline void Path(int x, int y) { //dep[y] 始终小于等于 dep[x]
if(x == y) return ;
x = fa[x]; int fx = top[x];
while(fx != top[y]) query0(dfn[fx], dfn[x]), x = fa[fx], fx = top[x];
query0(dfn[y], dfn[x]);
}
int main () {
read(n), read(m), read(A), read(B), read(Q);
for(int i = 2; i <= n; ++i)
read(fa[i]), addEdge(fa[i], i);
for(int i = 1; i <= n; ++i) gettmp(), a[i] = tmp;
dfs(1), dfs(1, 1), build(), read(q);
while(q--) {
read(op), read(x);
if(!op) gettmp(), modify(dfn[x]);
else {
read(y);
s0 = s1 = P();
Path(x, y), query1(dfn[x], dfn[x] + siz[x] - 1);
s0 = s0 * s1;
printf("%lld\n", s0.v[m]);
}
}
return 0;
}