题解 P4751 【动态dp【加强版】】
Great_Influence
2018-08-12 22:04:09
你们可以看看这个[宝贝](https://www.cnblogs.com/RabbitHu/p/9112811.html)来了解一下这个诡异的做法。
首先，需要前置技能[动态dp](https://www.luogu.org/problemnew/show/P4719)，然后才能够做这道题。
很明显，利用树剖套线段树直接维护矩阵的时间复杂度是$O(2^3qlog^2n)$的。再数据恶意卡的情况下，计算出来的复杂度高达$1e9$级，再算上线段树的巨大常数，基本上直接就$TLE$了。这时，我们需要一种更靠谱的复杂度来维护。
根据经验，在维护内容简单的情况下，如果某个信息可以用$splay$做到和线段树同级的维护，那么在$LCT$的意义下，是可以将两个$log$优化到一个$log$的。
那么我们的基本思路就出来了:就是不使用树剖套线段树来维护矩阵，而是改为使用$LCT$来维护矩阵。这样的时间复杂度就由$O(2^3q\log^2 n)$优化至$O(2^3q\log n)$。
不过$LCT$的常数过于巨大，并且树的形态固定，我们也不需要动态来维护一棵树。我们可以使用与$LCT$类似的数据结构来维护，同时也保证它的复杂度。
我们采用一棵普通的二叉搜索树来维护这个结构。其结构与$LCT$相似，存在轻边和重边之分，且一段重链用相连的一段二叉搜索树维护，而轻边直接用轻边挂在父亲节点下。这样，我们只要保证这个结构的深度不超过$O(\log n)$级，我们的复杂度就是正确的。
这时就有一个很简单的构造思想了。先将整棵树树链剖分(重链剖分)，再对于每个点，记录该点的轻子树的$size$之和+1，作为他的权。然后对于当前重链，记录它的加权重心，作为该重链的根，然后向两边递归建树。轻边还是一样挂在其父亲上。这样可以将树高严格卡在$O(\log n)$内。证明非常简单，每个点的父亲子树大小**至少是它自己子树大小的2倍**。这样经过不超过$\log n$次后，其子树大小会变成$n$。
代码(仅供参考)：
```cpp
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define pb push_back
#define Chkmax(a,b) a=a>b?a:b
#define Chkmin(a,b) a=a<b?a:b
#define mx(a,b) (a>b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;
namespace IO
{
const uint32 Buffsize=1<<15,Output=1<<24;
static char Ch[Buffsize],*St=Ch,*T=Ch;
inline char getc()
{
return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
x*=f;
}
template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++=48;
if(x<0)*nowps++='-',x=-x;
static uint32 sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using namespace IO;
inline void file()
{
#ifndef ONLINE_JUDGE
freopen("Ddp++.in","r",stdin);
freopen("Ddp++.out","w",stdout);
#endif
}
const int inf=0x3f3f3f3f,MAXN=1e6+7;
struct matrix
{
int s[2][2];
matrix(){s[0][0]=s[0][1]=s[1][0]=s[1][1]=-inf;}
matrix(int x){s[0][0]=s[1][1]=0;s[0][1]=s[1][0]=-inf;}
friend matrix operator*(matrix a,matrix b)
{
matrix c;
Chkmax(c.s[0][0],b.s[0][0]+a.s[0][0]);
Chkmax(c.s[0][0],b.s[0][1]+a.s[1][0]);
Chkmax(c.s[0][1],b.s[0][0]+a.s[0][1]);
Chkmax(c.s[0][1],b.s[0][1]+a.s[1][1]);
Chkmax(c.s[1][0],b.s[1][0]+a.s[0][0]);
Chkmax(c.s[1][0],b.s[1][1]+a.s[1][0]);
Chkmax(c.s[1][1],b.s[1][0]+a.s[0][1]);
Chkmax(c.s[1][1],b.s[1][1]+a.s[1][1]);
return c;
}
inline int getmx()
{return mx(mx(s[0][0],s[0][1]),mx(s[1][0],s[1][1]));}
};
static int n,m;
static int sz[MAXN],son[MAXN],g[MAXN][2],w[MAXN];
static struct edge
{
int v,nxt;
}p[MAXN<<1];
static int head[MAXN],e;
inline void add(int u,int v){p[++e]={v,head[u]};head[u]=e;}
void dfs(int u)
{
sz[u]=1;g[u][1]=w[u];
for(register int v=head[u];v;v=p[v].nxt)if(!sz[p[v].v])
{
dfs(p[v].v);sz[u]+=sz[p[v].v];
if(sz[p[v].v]>sz[son[u]])son[u]=p[v].v;
g[u][0]+=mx(g[p[v].v][0],g[p[v].v][1]);
g[u][1]+=g[p[v].v][0];
}
}
namespace bst
{
static matrix W[MAXN],S[MAXN];
static int so[MAXN][2],fa[MAXN],sta[MAXN],tp;
static int ssz[MAXN],rt;
inline void update(int u){S[u]=S[so[u][0]]*W[u]*S[so[u][1]];}
int build_tree(int l,int r)
{
if(l>r)return 0;
static int tot;tot=0;Rep(i,l,r)tot+=ssz[sta[i]];
for(register int i=l,cnt=ssz[sta[i]];i<=r;++i,cnt+=ssz[sta[i]])
if(cnt*2>=tot)
{
int rs=build_tree(l,i-1),ls=build_tree(i+1,r);
so[sta[i]][0]=ls,so[sta[i]][1]=rs;
fa[ls]=fa[rs]=sta[i];update(sta[i]);
return sta[i];
}
}
inline void getpoi(int u)
{W[u].s[0][0]=W[u].s[0][1]=**(g+u);W[u].s[1][0]=*(*(g+u)+1);}
int build(int top,int fr)
{
for(int t=top;t;fr=t,t=son[t])
{
for(register int v=head[t];v;v=p[v].nxt)
if(p[v].v^son[t]&&p[v].v^fr)
fa[build(p[v].v,t)]=t;
getpoi(t);
}
tp=0;
for(int t=top;t;t=son[t])
sta[++tp]=t,ssz[t]=sz[t]-sz[son[t]];
return build_tree(1,tp);
}
bitset<MAXN>isr;
void modify(int u,int val)
{
g[u][1]+=val-w[u];
w[u]=val;
static int dp0[2],dp1[2];
for(;u;u=fa[u])
{
dp0[0]=mx(S[u].s[0][0],S[u].s[0][1]);
dp0[1]=mx(S[u].s[1][0],S[u].s[1][1]);
getpoi(u);update(u);
dp1[0]=mx(S[u].s[0][0],S[u].s[0][1]);
dp1[1]=mx(S[u].s[1][0],S[u].s[1][1]);
if(isr.test(u))
{
g[fa[u]][0]+=mx(dp1[0],dp1[1])-mx(dp0[0],dp0[1]);
g[fa[u]][1]+=dp1[0]-dp0[0];
}
}
}
}
void dfs(int u,int fr)
{
if(!son[u])return;
g[u][0]-=mx(g[son[u]][0],g[son[u]][1]);
g[u][1]-=g[son[u]][0];
for(register int v=head[u];v;v=p[v].nxt)if(p[v].v^fr)dfs(p[v].v,u);
}
using namespace bst;
inline void init()
{
read(n);read(m);
Rep(i,1,n)read(w[i]);
static int u,v;
Rep(i,1,n-1)read(u),read(v),add(u,v),add(v,u);
dfs(1);
dfs(1,0);
W[0]=S[0]=matrix(0);
rt=build(1,0);
Rep(i,1,n)if(i^so[fa[i]][0]&&i^so[fa[i]][1])isr.set(i);
}
inline void solve()
{
static int lasans=0;
static int x,y;
Rep(i,1,m)
{
read(x);read(y);
x^=lasans;
modify(x,y);
write(lasans=S[rt].getmx());
}
flush();
}
int main()
{
file();
init();
solve();
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
```