题解：P10599 BZOJ2164 采矿

· · 题解

题目大意

给定矿点个数 n 和部下人数 m 与为生成数据 A，B，Q，点的父亲节点同 n 个矿点有几个部下带来的收益。进行 C 次询问，事件 0 为更改第 p 个矿点的收益，事件 1 为求 u，v 中 u 子树（包括 u）与 u 到 v 的链（u 应排除出选择，否则影响结果）怎样分配收益最大，其中 u 到 v 的链只能安排一次部下（个数不限）。

解题思路

看见选择出最大值可以想到 DP，处理链想到树链剖分，及将树进行树链剖分，再用线段树建树，线段树的每个节点存储一个数组 \operatorname{f}，\operatorname{g}（都为一维），在线段树中分别表示当前节点的所有叶子节点分配 i 个部下带来的最高收益（用 O(m^2) 的时间进行合并），当前节点的一个叶子节点分配 i 个部下带来的最高收益（用 O(m) 的时间进行合并）。子树内的答案只需区间查询（查询 \operatorname{f}），链上的只需树链剖分即可（查询 \operatorname{g}），时间复杂度分别为 O(m^2 \log n)，O(m \log^2 n)，修改则直接更改后合并，时间复杂度为 O(m^2 \log n)，总时间复杂度为 O(C(m^2 \log n + m \log^2 n))，可行。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long tou[20010],zui[20010],wei[20010],bian[20010],shen[20010],da[20010],
    son[20010],t,b[20010],fa[20010],n,m,B,A,Q,X,Y,p,c[51],d[51];
struct w{
    long long x,y;
}a[100010];
struct o{
    long long a[51],g[51];
}f[80010],uv[20010];
inline long long Getint()
{
    A=((A^B)+B/X+B*X)&Y;
    B=((A^B)+A/X+A*X)&Y;
    return (A^B)%Q;
}
void ww(long long die,long long ye)
{
    fa[die]=ye;
    da[die]=1;
    for(long long i=b[die];i;i=a[i].y)
    if(a[i].x!=ye)
    {
        shen[a[i].x]=shen[die]+1;
        ww(a[i].x,die);
        da[die]+=da[a[i].x];
    }
    for(long long i=b[die];i;i=a[i].y)
    if(a[i].x!=ye)
        if(da[son[die]]<da[a[i].x])
            son[die]=a[i].x;
}
void www(long long die,long long ye)
{
    if(son[die])
    {

        tou[son[die]]=tou[die];
        wei[son[die]]=++t;
        bian[wei[son[die]]]=son[die];
        zui[son[die]]=wei[son[die]];
        www(son[die],die);
        zui[die]=max(zui[die],zui[son[die]]);
    }
    for(long long i=b[die];i;i=a[i].y)
        if(a[i].x!=ye&&a[i].x!=son[die])
        {
            tou[a[i].x]=a[i].x;
            wei[a[i].x]=++t;
            zui[a[i].x]=wei[a[i].x];
            bian[wei[a[i].x]]=a[i].x;
            www(a[i].x,die);
            zui[die]=max(zui[die],zui[a[i].x]);
        }
}
void jian(long long k,long long l,long long r)
{
    if(l==r)
    {
        for(long long i=0;i<=m;i++)
            f[k].a[i]=uv[bian[l]].a[i],
            f[k].g[i]=uv[bian[l]].a[i];
        return;
    }
    long long mid=(l+r)/2;
    jian(k*2,l,mid);
    jian(k*2+1,mid+1,r);
    for(long long i=0;i<=m;i++)
        for(long long j=0;j<=i;j++)
            f[k].a[i]=max(f[k].a[i],f[k*2].a[j]+f[k*2+1].a[i-j]);
    for(long long i=0;i<=m;i++)
        f[k].g[i]=max(f[k*2].g[i],f[k*2+1].g[i]);
}
void gai(long long k,long long l,long long r,long long x)
{
    if(l==r)
    {
        for(long long i=0;i<=m;i++)
            f[k].a[i]=uv[bian[l]].a[i],
            f[k].g[i]=uv[bian[l]].a[i];
        return;
    }
    long long mid=(l+r)/2;
    if(x<=mid)gai(k*2,l,mid,x);
    if(x>mid)gai(k*2+1,mid+1,r,x);
    for(int i=0;i<=m;i++)
        f[k].g[i]=f[k].a[i]=0;
    for(long long i=0;i<=m;i++)
        for(long long j=0;j<=i;j++)
            f[k].a[i]=max(f[k].a[i],f[k*2].a[j]+f[k*2+1].a[i-j]);
    for(long long i=0;i<=m;i++)
        f[k].g[i]=max(f[k*2].g[i],f[k*2+1].g[i]);
}
void qui_f(long long k,long long l,long long r,long long x,long long y)
{
    if(x<=l&&r<=y)
    {
        for(long long i=m;i>=0;i--)
        for(long long j=i;j>=0;j--)
            c[i]=max(c[i],c[j]+f[k].a[i-j]);
        return;
    }
    long long mid=(l+r)/2;
    if(x<=mid)qui_f(k*2,l,mid,x,y);
    if(y>mid)qui_f(k*2+1,mid+1,r,x,y);
}
void qui_g(long long k,long long l,long long r,long long x,long long y)
{
    if(x<=l&&r<=y)
    {
        for(long long i=0;i<=m;i++)
            d[i]=max(d[i],f[k].g[i]);
        return;
    }
    long long mid=(l+r)/2;
    if(x<=mid)qui_g(k*2,l,mid,x,y);
    if(y>mid)qui_g(k*2+1,mid+1,r,x,y);
}
void llca(long long x,long long y)
{
    long long fx=tou[x],fy=tou[y];
    while(fx!=fy)
    {
        if(shen[fx]<shen[fy])
            swap(fx,fy),swap(x,y);
        qui_g(1,1,n,wei[fx],wei[x]);
        x=fa[fx];
        fx=tou[x];
    }
    if(shen[x]>shen[y])
        swap(x,y);
    qui_g(1,1,n,wei[x],wei[y]);
}
main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&m,&A,&B,&Q);
    X=pow(2,16);
    Y=pow(2,31)-1;
    for(long long i=2;i<=n;i++)
    {
        long long x;
        scanf("%lld",&x);
        a[++t].x=x;
        a[t].y=b[i];
        b[i]=t;
        a[++t].x=i;
        a[t].y=b[x];
        b[x]=t;
    }
    ww(1,1);
    t=0;
    tou[1]=1;
    wei[1]=++t;
    bian[wei[1]]=1;
    zui[1]=1;
    www(1,1);
    for(long long i=1;i<=n;i++)
    {
        uv[i].a[0]=0;
        for(long long j=1;j<=m;j++)
            uv[i].a[j]=Getint();
        sort(uv[i].a+1,uv[i].a+m+1);
    }
    jian(1,1,n);
    scanf("%lld",&p);
    while(p--)
    {
        long long z;
        scanf("%lld",&z);
        if(z==0)
        {
            long long x;
            scanf("%lld",&x);
            uv[x].a[0]=0;
            for(long long j=1;j<=m;j++)
                uv[x].a[j]=Getint();
            sort(uv[x].a+1,uv[x].a+m+1);
            gai(1,1,n,wei[x]);
        }
        else
        {
            for(long long i=0;i<=m;i++)
                c[i]=d[i]=0;
            long long u,v,uu;
            scanf("%lld%lld",&u,&v);
            uu=fa[u];
            if(shen[uu]>=shen[v])
                llca(uu,v);
            qui_f(1,1,n,wei[u],zui[u]);
            long long s=0;
            for(long long i=0;i<=m;i++)
                s=max(s,c[i]+d[m-i]);
            printf("%lld\n",s);
        }
    }
}