【题目描述】：
    浩浩荡荡的cg大军发现了一座矿产资源极其丰富的城市，他们打算在这座城市实施新的采矿战略。
　　这个城市可以看成一棵有n个节点的有根树，我们把每个节点用1到n的整数编号。为了方便起见，对于任何一个非根节点v，它任何一个祖先的编号都严格小于v。树上的每个节点表示一个矿点，每条边表示一条街道。
　　作为cg大军的一个小队长，你拥有m个部下。你有一张二维的动态信息表，用Ti,j表示第i行第j列的数据。当你被允许开采某个区域时，你可以将你的部下分配至各个矿点。在第i个矿点安排j个人可以获得Ti,j单位的矿产。
　　允许开采的区域是这样描述的：给你一对矿点(u,v)，保证v是u的祖先（这里定义祖先包括u本身）；u为你控制的区域，可以在以u为根的子树上任意分配部下；u到v的简单路径（不包括u但包括v，若u=v则包括u）为探险路径，在该路径上你可以选择至多一个矿点安排部下。你这次开采的收益为安排有部下的矿点的收益之和。
【题目解法】：
    不建议在bzoj上看题目，排版简直...TAT

http://www.tsinsen.com/ViewGProblem.page?gpid=A1219

    按照dfs序进行树链剖分，这样既可以维护子树信息，又可以维护链上信息
    令f[i]表示设置任意数量的矿点时放置i个人的最大价值
    令g[i]表示设置一个矿点是放置i个人的最大价值
    将f,g放在线段树每一个结点中
    合并的时候：
    对于f：now.f[i]=max(lc.f[j]+rc.f[i-j])
    对于g：now.g[i]=max(lc.g[i],rc.g[i])
    修改的复杂度为O(C*m^2 log n)
    查询的复杂度为O(C*m log^2 n+C*m)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=20005;
const int M=55;
const int X=1<<16;
const int Y=(1LL<<31)-1LL;
struct edge {int x,next;} b[N];
int n,people,m,L[N],R[N],A,B,Q,tot,a[N];
int top[N],size[N],son[N],dep[N],fa[N]; long long ans;
struct node
{
    long long f[M],g[M];
    inline void clear()
    {
        for (int i=0; i<=people; i++) f[i]=g[i]=0;
    }
} tree[N*4];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void addedge(int x,int y)
{
    ++tot;
    b[tot].x=y;
    b[tot].next=a[x];
    a[x]=tot;
}
void init()
{
    n=getint(); people=getint(); A=getint(); B=getint(); Q=getint(); dep[1]=1;
    for (int i=2; i<=n; i++) fa[i]=getint(),addedge(fa[i],i),dep[i]=dep[fa[i]]+1; tot=0;
}
void dfs(int x)
{
    size[x]=1; int k=0;
    for (int p=a[x];p;p=b[p].next)
    {
        int pp=b[p].x; dfs(pp); size[x]+=size[pp];
        if (size[pp]>k) k=size[pp],son[x]=pp;
    }
}
void DFS(int x,int anc)
{
    L[x]=++tot; top[x]=anc; if (son[x]!=0) DFS(son[x],anc);
    for (int p=a[x];p;p=b[p].next) if (b[p].x!=son[x]) DFS(b[p].x,b[p].x);
    R[x]=tot;
}
namespace Graph
{
    inline int GetInt()
    {
        /*
        A←((A xor B)+(B div X)+(B * X))and Y
        B←((A xor B)+(A div X)+(A * X))and Y
        返回(A xor B)mod Q
        */
        A=((A^B)+(B/X)+(B*X))&Y;
        B=((A^B)+(A/X)+(A*X))&Y;
        return (A^B)%Q;
    }
    inline void MakeGraph(long long a[])
    {
        for (int i=1; i<=people; i++) a[i]=GetInt();
        sort(a+1,a+people+1); a[0]=0;
        //for (int i=1; i<=people; i++) printf("%d ",a[i]);
        //printf("\n");
    }
}
inline node updata(const node &lc,const node &rc)
{
    node now; now.clear();
    for (int i=1; i<=people; i++) for (int j=0; j<=i; j++) now.f[i]=max(now.f[i],lc.f[j]+rc.f[i-j]);
    for (int i=1; i<=people; i++) now.g[i]=max(lc.g[i],rc.g[i]);
    return now;
}
void modify(int p,int l,int r,int x)
{
    if (l==r)
    {
        Graph::MakeGraph(tree[p].f);
        for (int i=0; i<=people; i++) tree[p].g[i]=tree[p].f[i];
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid) modify(p*2,l,mid,x); else modify(p*2+1,mid+1,r,x);
    tree[p]=updata(tree[p*2],tree[p*2+1]);
}
void build()
{
    for (int i=1; i<=n; i++) modify(1,1,n,L[i]);
}
node ask(int p,int l,int r,int ll,int rr)
{
    if ((l==ll)&&(r==rr)) return tree[p]; int mid=(l+r)/2;
    if (rr<=mid) return ask(p*2,l,mid,ll,rr);
    else if (ll>mid) return ask(p*2+1,mid+1,r,ll,rr);
    else return updata(ask(p*2,l,mid,ll,mid),ask(p*2+1,mid+1,r,mid+1,rr));
}
node ask(int x,int y)
{
    node now; now.clear();
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        now=updata(now,ask(1,1,n,L[top[x]],L[x]));
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    now=updata(now,ask(1,1,n,L[x],L[y]));
    return now;
}
void Ask(int x,int y)
{
    node Tree=ask(1,1,n,L[x],R[x]); ans=0;
    node Link; Link.clear(); if (x!=y) Link=ask(fa[x],y);
    for (int i=0; i<=people; i++) ans=max(ans,Tree.f[i]+Link.g[people-i]);
    printf("%lld\n",ans);
}
void solve()
{
    m=getint();
    for (int i=1; i<=m; i++)
    {
        int opt=getint();
        if (opt==0) {int x=getint(); modify(1,1,n,L[x]);}
        if (opt==1) {int x=getint(),y=getint(); Ask(x,y);}
    }
}
int main()
{
    init();
    dfs(1);
    DFS(1,1);
    build();
    solve();
    return 0;
}