1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long int64;
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e4+5, M = 50+5;
const int X = 1<<16, Y = ~0u>>1;
struct Edge
{
int next, to;
Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N];
int tot, head[N];
inline void add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }
int n, m, A, B, Q, T;
int64 tab[N][M];
inline int getint()
{
A=((A^B)+(B/X)+(B*X))&Y;
B=((A^B)+(A/X)+(A*X))&Y;
return (A^B)%Q;
}
int fa[N], top[N], size[N], d[N], dfn[N], nfd[N], son[N], t;
void dfs(int x)
{
size[x] = 1, d[x] = d[fa[x]]+1;
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to; dfs(y); size[x] += size[y];
son[x] = size[son[x]]>size[y]?son[x]:y;
}
}
void dfs(int x, int topf)
{
dfn[x] = ++t, top[x] = topf, nfd[t] = x;
if(son[x]) dfs(son[x], topf);
for(int i = head[x]; i; i = edge[i].next)
{
int y = edge[i].to;
if(son[x] != y) dfs(y, y);
}
}
struct Bag
{
int64 f[M];
Bag() { for(int i = 0; i <= m; ++i) f[i] = 0; }
Bag operator + (const Bag &_) const
{
Bag ret;
for(int i = 0; i <= m; ++i) ret.f[i] = max(f[i], _.f[i]);
return ret;
}
Bag operator * (const Bag &_) const
{
Bag ret;
for(int i = 0; i <= m; ++i)
for(int j = 0; j <= m-i; ++j)
ret.f[i+j] = max(ret.f[i+j], f[i]+_.f[j]);
return ret;
}
}b1[N<<2], b2[N<<2];
void pushup(int x) { b1[x] = b1[x<<1]+b1[x<<1|1]; b2[x] = b2[x<<1]*b2[x<<1|1]; }
void build(int x, int l, int r)
{
if(l == r) return (void)(memcpy(b1[x].f, tab[nfd[l]], sizeof(b1[x].f)), b2[x] = b1[x]);
int mid = (l+r)>>1; build(x<<1, l, mid); build(x<<1|1, mid+1, r); pushup(x);
}
void change(int x, int l, int r, int pos)
{
if(l == r) return (void)(memcpy(b1[x].f, tab[nfd[l]], sizeof(b1[x].f)), b2[x] = b1[x]);
int mid = (l+r)>>1;
if(pos <= mid) change(x<<1, l, mid, pos);
else change(x<<1|1, mid+1, r, pos);
pushup(x);
}
Bag query1(int x, int l, int r, int ql, int qr)
{
if(ql <= l&&r <= qr) return b1[x];
int mid = (l+r)>>1; Bag ret;
if(ql <= mid) ret = ret+query1(x<<1, l, mid, ql, qr);
if(qr > mid) ret = ret+query1(x<<1|1, mid+1, r, ql, qr);
return ret;
}
Bag query2(int x, int l, int r, int ql, int qr)
{
if(ql <= l&&r <= qr) return b2[x];
int mid = (l+r)>>1; Bag ret;
if(ql <= mid) ret = ret*query2(x<<1, l, mid, ql, qr);
if(qr > mid) ret = ret*query2(x<<1|1, mid+1, r, ql, qr);
return ret;
}
Bag query(int x, int y)
{
Bag ret; if(x == y) return ret; x = fa[x];
while(top[x] != top[y]) ret = ret+query1(1, 1, n, dfn[top[x]], dfn[x]), x = fa[top[x]];
ret = ret+query1(1, 1, n, dfn[y], dfn[x]);
return ret;
}
int main()
{
n = read(), m = read(), A = read(), B = read(), Q = read();
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j) tab[i][j] = getint();
sort(tab[i]+1, tab[i]+m+1);
}
for(int x = 2; x <= n; ++x) add(fa[x] = read(), x);
dfs(1); dfs(1, 1); build(1, 1, n);
T = read();
while(T--)
{
int opt = read(), x = read(), y;
if(opt == 0)
{
for(int i = 1; i <= m; ++i) tab[x][i] = getint();
sort(tab[x]+1, tab[x]+m+1);
change(1, 1, n, dfn[x]);
}
else
{
y = read(); Bag ans = query(x, y)*query2(1, 1, n, dfn[x], dfn[x]+size[x]-1);
printf("%lld\n", ans.f[m]);
}
}
return 0;
}
|