Luogu P4719 동적 dp

전송 문
문제 풀이: 일상적인 문 제 를 쓸 수 없다. 메모리 보드 는 이것 이 동태 적 인 것 이 아니 라 고 가정 한다. f [i] [0 / 1] f [i] [0 / 1] f [1] f [i] [0 / 1] 을 i 번 째 점 에서 선택 하지 않 고 선택 한 답 으로 설정 한다.그럼 f [i] [0] = ∑ max ⁡ (f [j] [0]] [0]], f [j] [1]), f [i] [1] = △ △ △ △ △ △ △ f [j] [0] [0] + v [i]. f [[i]] [0] = \ \ \ sum\ \ \ \ \ \ \ \ \ \ \ \ sumf [j] [1]), f [j] [1]), f [2] [1] = \ \ sumf [j] [0] [0] + v [0] + v [[[0]. f [0] = ∑ max (f [j] [0] [0], f [j] [0]], f [1], f [j]]], f [1]] [1]]]]... 그 후에 한 점 의 가중치 를 수정 하 는 것 은 위의 값 에 가장 많은 영향 을 미친다.그리고 g [i] [0 / 1] g [0 / 1] g [0 / 1] [0 / 1] 을 가 벼 운 아들 의 dp 값 만 을 고려 합 니 다.f [i] [0] = max ⁡ (f [s o n] [0], f [s o n] [0]] [1]) + g [i] [0], f [i] [i] [1] = f [s o n] [0] [0] + g [i] [1]. f [i] [0] = \ \ \ max (f [son] [0], f [son]] [1], f [son] [1]) + g [0] [0], f [i] [0] [0] [f [son]] [0]] [1] = f [son] [0] + g [0] [0]]] [1]]. f [0]. [0]. f[[]]]] [0]] = max (f [son] [0 f [i] [1] = f [son] [0] + g [i] [1]. 그리고 인류의 지혜 를 이용 하여 곱셈 을 덧셈 으로 정의 할 수 있다.덧셈 을 max 로 정의 하고 행렬 을 만 듭 니 다. (f [i] [0] f [i] [1] = (g [i] [0] g [i] [0] g [i] [1] - 표시)× ( f [ s o n ] [ 0 ] f [ s o n ] [ 1 ] ) \begin{pmatrix} f[i][0] \\ f[i][1] \end{pmatrix}=\begin{pmatrix} g[i][0] & g[i][0] \\ g[i][1] & -\infty \end{pmatrix}\times \begin{pmatrix} f[son][0] \\ f[son][1] \end{pmatrix} (f[i][0]f[i][1]​)=(g[i][0]g[i][1]​g[i][0]−∞​)×(f [son] [0] f [son] [1]) 그리고 나 무 를 갈 라 서 선분 수 를 유지 할 수 있 습 니 다.수정 할 때 체인 f 값 을 바 꾸 고 체인 상단 g 값 을 바 꾸 면 됩 니 다.모 르 겠 어 요. 모 라 는 문 제 는 오른쪽 아래 에서 0 을 뽑 아 도 넘 어 갈 수 있어 요.
코드:

#include
#include
#include
#define maxn 100005
using namespace std;
int n,m,a[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn],tid[maxn],ed[maxn],rnk[maxn],ccnt,g[maxn][2];
struct node { int v; node *nxt; } edge[maxn*2],*head[maxn],*ncnt;
struct mat { int f[2][2]; } tree[maxn*4],val[maxn];
mat operator * (mat a,mat b)
{
    mat c;
    memset(c.f,0,sizeof(c.f));
    for(int k=0;k<2;k++)
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++) c.f[i][j]=max(c.f[i][j],a.f[i][k]+b.f[k][j]);
    return c;
}
void addedge(int u,int v)
{
    ncnt++;
    ncnt->v=v,ncnt->nxt=head[u];
    head[u]=ncnt;
}
void dfs1(int u,int f,int d)
{
    dep[u]=d,fa[u]=f,siz[u]=1,g[u][1]=a[u];
    for(node *p=head[u];p;p=p->nxt)
    {
        int v=p->v;
        if(v==f) continue;
        dfs1(v,u,d+1); siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
        g[u][0]+=max(g[v][0],g[v][1]),g[u][1]+=g[v][0];
    }
}
void dfs2(int u,int tp)
{
    tid[u]=++ccnt,rnk[ccnt]=u,top[u]=tp;
    if(!son[u]) { ed[u]=u; return; }
    dfs2(son[u],tp); ed[u]=ed[son[u]];
    for(node *p=head[u];p;p=p->nxt)
    {
        int v=p->v;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
void Build(int i,int l,int r)
{
    if(l==r)
    {
        int u=rnk[l],g0=0,g1=a[u];
        for(node *p=head[u];p;p=p->nxt)
        {
            int v=p->v;
            if(v!=fa[u]&&v!=son[u]) g0+=max(g[v][0],g[v][1]),g1+=g[v][0];
        }
        tree[i].f[0][0]=tree[i].f[0][1]=g0,tree[i].f[1][0]=g1;
        val[l]=tree[i];
        return;
    }
    int mid=(l+r)>>1;
    Build(i<<1,l,mid); Build(i<<1|1,mid+1,r);
    tree[i]=tree[i<<1]*tree[i<<1|1];
}
mat Query(int i,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr) return tree[i];
    int mid=(l+r)>>1;
    if(qr<=mid) return Query(i<<1,l,mid,ql,qr);
    else if(ql>mid) return Query(i<<1|1,mid+1,r,ql,qr);
    return Query(i<<1,l,mid,ql,qr)*Query(i<<1|1,mid+1,r,ql,qr);
}
void Modify(int i,int l,int r,int p)
{
    if(l==r) { tree[i]=val[l]; return; }
    int mid=(l+r)>>1;
    if(p<=mid) Modify(i<<1,l,mid,p);
    else Modify(i<<1|1,mid+1,r,p);
    tree[i]=tree[i<<1]*tree[i<<1|1];
}
void Modify(int u,int x)
{
    val[tid[u]].f[1][0]+=x-a[u]; a[u]=x;
    while(u)
    {
        mat la=Query(1,1,n,tid[top[u]],tid[ed[u]]);
        Modify(1,1,n,tid[u]);
        mat cur=Query(1,1,n,tid[top[u]],tid[ed[u]]);
        u=fa[top[u]];
        val[tid[u]].f[0][0]+=max(cur.f[0][0],cur.f[1][0])-max(la.f[0][0],la.f[1][0]);
        val[tid[u]].f[0][1]=val[tid[u]].f[0][0];
        val[tid[u]].f[1][0]+=cur.f[0][0]-la.f[0][0];
    }
}
int main()
{
    scanf("%d%d",&n,&m); ncnt=&edge[0];
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v); addedge(v,u);
    }
    dfs1(1,0,1); dfs2(1,1);
    Build(1,1,n);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        Modify(x,y);
        mat t=Query(1,1,n,tid[1],tid[ed[1]]);
        printf("%d
",max(t.f[0][0],t.f[1][0]));
    }
}