【弱校胡策】2016.4.14(bzoj 2164)最短路+状圧DP+マトリックス乗算+Gauss消元+樹鎖断分+線分樹+リュックDP

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL; 
const int SZ = 100010;
const int INF = 1000000010;

int n,m,A,B,Q;

int get_int()
{
    const int X = 1 << 16;
    const int Y = (1ll << 31ll) - 1ll;
    A=((A^B)+(B/X)+(B*X))&Y;
    B=((A^B)+(A/X)+(A*X))&Y;
    return (A^B)%Q;
}

void scan(int &n)
{
    n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') { n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
}

int head[SZ],nxt[SZ],to[SZ];

void build(int f,int t)
{
    static int tot = 1;
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int top[SZ],sz[SZ],son[SZ],fa[SZ],deep[SZ];

void dfs_1(int u,int f)
{
    fa[u] = f;
    deep[u] = deep[f] + 1;
    sz[u] = 1;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        dfs_1(v,u);
        sz[u] += sz[v];
        if(!son[u] || sz[son[u]] < sz[v]) son[u] = v;
    }
}

int pre[SZ],suf[SZ],dfs_clock = 0,intre[SZ];

void dfs_2(int u,int topu)
{
    top[u] = topu;
    pre[u] = ++ dfs_clock;
    intre[dfs_clock] = u;
    if(son[u]) dfs_2(son[u],topu);
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(v == son[u]) continue;
        dfs_2(v,v);
    }
    suf[u] = ++ dfs_clock;
}

int val[SZ][60];

struct segment{
    int l,r;
    int mx1[60],mx2[60]; //     
}tree[SZ << 2];

void update(int p)
{
    memset(tree[p].mx1,0,sizeof(tree[p].mx1));
    int lch = p << 1,rch = p << 1 | 1;
// for(int i = 0;i <= m;i ++)
// for(int j = 0;j <= m - i;j ++)
// tree[p].mx1[i + j] = max(tree[p].mx1[i + j],tree[lch].mx1[i] + tree[rch].mx1[j]);
    for(int i = m;i >= 0;i --)
        for(int j = i;j >= 0;j --)
            tree[p].mx1[i] = max(tree[p].mx1[i],tree[lch].mx1[j] + tree[rch].mx1[i - j]);

    for(int i = 1;i <= m;i ++) tree[p].mx2[i] = max(tree[lch].mx2[i],tree[rch].mx2[i]);
}

void build(int p,int l,int r)
{
    tree[p].l = l; tree[p].r = r;
    if(l == r)
    {
        for(int i = 1;i <= m;i ++)
            tree[p].mx1[i] = tree[p].mx2[i] = val[intre[l]][i];
        return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid); build(p << 1 | 1,mid + 1,r);
    update(p);
}

void change(int p,int pos)
{
    if(tree[p].l == tree[p].r)
    {
        for(int i = 1;i <= m;i ++)
            tree[p].mx1[i] = tree[p].mx2[i] = val[intre[pos]][i];
        return ;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(pos <= mid) change(p << 1,pos);
    else change(p << 1 | 1,pos);
    update(p);
}

int ans1[60],ans2[60];

void ask_ans1(int p,int l,int r)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        for(int i = m;i >= 0;i --)
            for(int j = i;j >= 0;j --)
                ans1[i] = max(ans1[i],ans1[i - j] + tree[p].mx1[j]);
        return ;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) ask_ans1(p << 1,l,r);
    if(mid < r) ask_ans1(p << 1 | 1,l,r);
}

void ask_ans2(int p,int l,int r)
{
    if(l <= tree[p].l && tree[p].r <= r)
    {
        for(int i = 1;i <= m;i ++)
            ans2[i] = max(ans2[i],tree[p].mx2[i]);
        return ;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) ask_ans2(p << 1,l,r);
    if(mid < r) ask_ans2(p << 1 | 1,l,r);
}

void find_ans2(int x,int y)
{
    int fx = top[x],fy = top[y];
    while(fx != fy)
    {
        if(deep[fx] < deep[fy]) swap(fx,fy),swap(x,y);
        ask_ans2(1,pre[fx],pre[x]);
        x = fa[fx]; fx = top[x];
    }
    if(deep[x] > deep[y]) swap(x,y);
    ask_ans2(1,pre[x],pre[y]);
}

int main()
{
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);       
    scan(n); scan(m); scan(A); scan(B); scan(Q);
    for(int i = 2;i <= n;i ++)
    {
        int x;
        scan(x);
        build(x,i);
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
            val[i][j] = get_int();
        sort(val[i] + 1,val[i] + 1 + m);
    }
    dfs_1(1,0); dfs_2(1,1);
    build(1,1,dfs_clock);
    int C;
    scan(C);
    while(C --)
    {
        int opt;
        scan(opt);
        if(opt == 0)
        {
            int p;
            scan(p);
            for(int j = 1;j <= m;j ++)
                val[p][j] = get_int();
            sort(val[p] + 1,val[p] + 1 + m);
            change(1,pre[p]);
        }
        else
        {
            memset(ans1,0,sizeof(ans1));
            memset(ans2,0,sizeof(ans2));
            int u,v;
            scan(u); scan(v);
            ask_ans1(1,pre[u],suf[u]);
            if(u != v) find_ans2(v,fa[u]);
            int ans = 0;
            for(int i = 0;i <= m;i ++)
                ans = max(ans,ans1[i] + ans2[m - i]);
            printf("%d
",ans);
        }
    }
    fclose(stdin); fclose(stdout);  
    return 0;
}