$$f_{u,1}=\sum_{v\in son}f_{v,0}$$
$$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$

$$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$

$$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$

$$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$

$$f_{u,1}=g_{u,1}+f_{heavyson,0}$$

$$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$

$${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} &0\end{array} \right ]}\times{\left[ \begin{array}{cc}f_{i+1,0} & f_{i,0}\\ f_{i+1,1} & 0 \end{array} \right ]}={\left[ \begin{array}{cc}f_{i,0}\\ f_{i,1} \end{array} \right ]}$$

### 伪代码

#include
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define maxn 1000100
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn<<1];
struct Matrix{
ll g[2][2];
Matrix operator * (const Matrix &x) const{
Matrix r;
for (register int i=0;i<2;++i)
for (register int j=0;j<2;++j)
for (register int k=0;k<2;++k)
r.g[i][j]=max(r.g[i][j],g[i][k]+x.g[k][j]);
return r;
}
}val[maxn],tree[maxn];
int cnt,n,m;
int top[maxn],id[maxn],fa[maxn];
int siz[maxn],son[maxn],nv[maxn],ed[maxn];
ll f[maxn][2];
}
void Pre_Work(int u,int f){
fa[u]=f,siz[u]=1;
int maxson=-1;
int v=l[i].to;
if (v==f) continue;
Pre_Work(v,u);
siz[u]+=siz[v];
if (siz[v]>maxson)
maxson=siz[v],son[u]=v;
}
}
void Re_Build(int u,int topf){
top[u]=topf;wid[id[u]=++cnt]=u;
nv[cnt]=vl[u];
if (!son[u]) {ed[topf]=cnt;return;}
Re_Build(son[u],topf);
int v=l[i].to;
if (v==fa[u]||v==son[u]) continue;
Re_Build(v,v);
}
}
void Get_f(int u){
f[u][1]=max(0,vl[u]);
int v=l[i].to;
if (v==fa[u]) continue;
Get_f(v);
f[u][1]+=f[v][0];
f[u][0]+=max(f[v][0],f[v][1]);
}
}
void Build(int l,int r,int p){
if (l==r){
ll g0=0,g1=a[wid[l]];
int v=l[i].to;
if (v==fa[u]||v==son[u]) continue;
g0+=max(f[v][0],f[v][1]);
g1+=f[v][0];
}
tree[p].g[0][0]=tree[p].g[0][1]=g0;
tree[p].g[1][0]=g1;
return;
}
Build(l,mid,ls),Build(mid+1,r,rs);
tree[p]=tree[ls]*tree[rs];
}
void Update(int l,int r,int t,int p){
if (l==r){tree[p]=val[l];return;}
if (t<=mid) Update(l,mid,t,ls);
else Update(r,mid+1,t,rs);
tree[p]=tree[ls]*tree[rs];
}
Matrix Query(int l,int r,int L,int R,int p){
if (l>=L&&r<=R) return tree[p];
if (R<=mid) return Query(l,mid,L,R,ls);
if (L>mid) return Query(mid+1,r,L,R,rs);
return Query(l,mid,L,R,ls)*Query(mid+1,r,L,R,rs);
}
return Query(1,n,id[top[u]],ed[top[u]],1);
}
void Path_Change(int u,int x){
val[id[u]].g[1][0]+=x-vl[u];
vl[u]=x;
Matrix lst,cur;
while(u){
Update(1,n,id[u],1);
u=fa[top[u]];
val[id[u]].g[0][0]+=max(cur.g[0][0],cur.g[1][0])-max(lst.g[0][0],lst.g[1][0]);
val[id[u]].g[0][0]=val[id[u]].g[0][0];
val[id[u]].g[1][0]+=cur.g[0][0]-lst.g[0][0];
}
}
int main(){
scanf("%d%d",&n,&m);
for (register int i=1;i<=n;++i)
scanf("%d",vl+i);
for (register int i=1,a,b;i
 
 Share Topic Study 【LuoGu T44990】不认识 / 题解 原题链接 [https://www.luogu.org/problemnew/show/T44990] 题意简述 有 $n$ 个同学站成一排（… 29 Nov 2018 【杂谈】对崔永元纪录片的不严谨分析与解读 2014年3月1号，崔永元先生公布了自费 100 万元拍摄的赴美考察转基因纪录片，片长 68 分钟 28 秒。我们先可以回顾一下它。 现在是 2018年11月。… 24 Nov 2018 
 
 
 Zepto's © 2024 Data & privacy Contact → Published with Ghost • Theme Attila • System theme 
 $(document).ready(function () { var viewport =$(window); var post = $('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() {$('pre code').each(function(i, e) { // Code highlight hljs.highlightElement(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code =$(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100);$('.progress-bar').css('width', progress + '%'); (progress > 100) ? $('.progress-container').addClass('complete'):$('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); });