题解 P4751 【【模板】"动态DP"&动态树分治（加强版）】

· · 题解

突然心血来潮交了一发以前的90分LCT代码，居然过了,还只要2.4s？？

不禁回忆起了我以前卡了两天还差0.3s的绝望。

于是我就来提供一个阅读性比较好的LCT代码，并提供一个卡常的方法。

LCTNB!!!

1.循环展开。

2.IO优化

3.#pragma GCC optimize

125行你值得拥有

/*
@Date    : 2019-08-16 11:34:40
@Author  : Adscn ([email protected])
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
const int N=1e6+7;
struct edge{
    int v,nxt;
}e[N<<1];
int head[N],cnt;
int n,m;
int a[N],dp[N][2];
inline void add(const int &u,const int &v){e[++cnt]=(edge){v,head[u]},head[u]=cnt;}
inline int max(const int &a,const int &b){return a>b?a:b;}
namespace LCT{
    #define ls(x) (c[x][0])
    #define rs(x) (c[x][1])
    #define s(x,k) (c[x][k])
    int fa[N],c[N][2];
    struct matrix{
        int a[4];
        inline int &operator [] (const int &x){return a[x];}
        inline const int &operator [] (const int &x)const{return a[x];}
        inline matrix operator * (const matrix &b)const{
            matrix c;
            c[0]=max(a[1]+b[2],a[0]+b[0]);
            c[1]=max(a[0]+b[1],a[1]+b[3]);
            c[2]=max(a[3]+b[2],a[2]+b[0]);
            c[3]=max(a[3]+b[3],a[2]+b[1]);
            return c;
        }
    }ret[N],val[N];
    inline bool ws(const int &x){return ls(fa[x])^x;}
    inline bool nrt(const int &x){return ls(fa[x])==x||rs(fa[x])==x;}
    inline void pushup(const int &x){
        ret[x]=val[x];
        if(ls(x))ret[x]=ret[ls(x)]*ret[x];
        if(rs(x))ret[x]=ret[x]*ret[rs(x)];
    }
    inline void rotate(const int &x){
        int p=fa[x],g=fa[p],t=ws(x),w=s(x,!t);
        if(nrt(p))s(g,ws(p))=x;s(x,!t)=p,s(p,t)=w;
        fa[w]=p;fa[p]=x,fa[x]=g;
        pushup(p);
    }
    inline void Splay(const int &x)
    {
        while(nrt(x))
        {
            int p=fa[x];
            if(nrt(p))rotate(ws(x)^ws(p)?x:p);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(register int x)
    {
        for(register int y=0;x;x=fa[y=x]){
            Splay(x);
            val[x][0]+=max(ret[rs(x)][0],ret[rs(x)][2])-max(ret[y][0],ret[y][2]),val[x][2]+=ret[rs(x)][0]-ret[y][0];
            val[x][1]=val[x][0];
            rs(x)=y,pushup(x);
        }
    }
    inline void modify(const int &x,const int &y)
    {
        access(x),Splay(x);
        val[x][2]-=a[x]-y,a[x]=y;
        pushup(x);
    }
}
using namespace LCT;
inline void dfs(const int &p)
{
    for(int i=head[p],v;i;i=e[i].nxt)
        if((v=e[i].v)^fa[p])
            fa[v]=p,dfs(v),dp[p][0]+=max(dp[v][0],dp[v][1]),dp[p][1]+=dp[v][0];
    val[p][0]=val[p][1]=dp[p][0],val[p][2]=(dp[p][1]+=a[p]),ret[p]=val[p],val[p][3]=-1e9;
}
int main(void)
{
    n=gi,m=gi;
    for(int i=1;i<=n;++i)a[i]=gi;
    for(int i=1,u,v;i<n;++i)u=gi,v=gi,add(u,v),add(v,u);
    dfs(1);
    int lastans=0;
    while(m--)
    {
        int x=gi,y=gi;
        modify(x^lastans,y),Splay(1);
        pi(lastans=max(ret[1][0],ret[1][2]),'\n');
    }
    return 0;
}