我现在还是不明白为什么NOIPd2t3会是一道动态dp……

首先关于动态dp可以看

然后这里就是把把矩阵给改一改，改成这个形式\[\left[dp_{i-1,0},dp_{i-1,1}\right]\times \left[\begin{matrix}\infty&ldp_{i,1}\\ldp_{i,0}&ldp_{i,1}\end{matrix}\right]\]

然后就是改成\(longlong\)，以及改一改取最小。关于强制取或不取，只要让值加上一个极大值或减去极大值就可以了

于是这么想着并交上去的我就调了一天

这里最主要的问题是，因为矩乘之后，第二行的两个数才是\(dp_{i,0}\)和\(dp_{i,1}\)，然后没发现这点，于是就没有于是了……

//minamoto#include
    
     #define R register#define ll long long#define mx 1e10#define inf 1e12#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}inline void getstr(){char ch;while((ch=getc())<'A'||ch>'Z');while((ch=getc())>='A'&&ch<='Z');}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e5+5;inline ll min(R ll x,R ll y){return x
      
       y?x:y;}struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int sz[N],lsz[N],val[N],son[N],fat[N],n,m;void dfs(int u,int fa){    sz[u]=1;go(u)if(v!=fa){        fat[v]=u,dfs(v,u),sz[u]+=sz[v];        if(sz[v]>sz[son[u]])son[u]=v;    }lsz[u]=sz[u]-sz[son[u]];}struct Matrix{    ll a[2][2];    Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=inf;}    Matrix(R int x){a[0][0]=a[1][1]=0,a[0][1]=a[1][0]=inf;}    inline ll mn(){return min(min(a[0][0],a[0][1]),min(a[1][0],a[1][1]));}    inline ll* operator [](const int &x){return a[x];}    Matrix operator *(Matrix b){        Matrix res;        res[0][0]=min(a[0][0]+b[0][0],a[0][1]+b[1][0]);        res[0][1]=min(a[0][0]+b[0][1],a[0][1]+b[1][1]);        res[1][0]=min(a[1][0]+b[0][0],a[1][1]+b[1][0]);        res[1][1]=min(a[1][0]+b[0][1],a[1][1]+b[1][1]);        return res;    }}mul[N],w[N];int ch[N][2],fa[N],st[N],top,rt;bool vis[N];inline void upd(R int u){mul[u]=mul[ch[u][0]]*w[u]*mul[ch[u][1]];}inline void pd(R int u,R int v){    w[u][0][1]+=mul[v].mn(),w[u][1][1]=w[u][0][1],w[u][1][0]+=mul[v][1][1],fa[v]=u;}inline bool is(R int u){return ch[fa[u]][0]!=u&&ch[fa[u]][1]!=u;}inline void init(){fp(i,1,n)w[i][0][1]=w[i][1][1]=val[i],w[i][1][0]=0,mul[i]=w[i];}int sbuild(int l,int r){    if(l>r)return 0;int tot=0;fp(i,l,r)tot+=lsz[st[i]];    for(int i=l,now=lsz[st[i]];i<=r;++i,now+=lsz[st[i]])    if(now*2>=tot){        ch[st[i]][0]=sbuild(i+1,r),ch[st[i]][1]=sbuild(l,i-1);        fa[ch[st[i]][0]]=fa[ch[st[i]][1]]=st[i],upd(st[i]);        return st[i];    }}int build(int u){    for(int p=u;p;p=son[p])vis[p]=1;    for(int p=u;p;p=son[p])go(p)if(!vis[v])pd(p,build(v));    top=0;for(int p=u;p;p=son[p])st[++top]=p;    return sbuild(1,top);}void update(int u,int vva){    w[u][0][1]+=vva?-mx:mx,w[u][1][1]=w[u][0][1];    for(R int p=u;p;p=fa[p])if(is(p)&&fa[p]){        w[fa[p]][0][1]-=mul[p].mn(),w[fa[p]][1][1]=w[fa[p]][0][1];        w[fa[p]][1][0]-=mul[p][1][1],upd(p);        w[fa[p]][0][1]+=mul[p].mn(),w[fa[p]][1][1]=w[fa[p]][0][1];        w[fa[p]][1][0]+=mul[p][1][1];    }else upd(p);}int f[N][2];void dp(int u,int fa){    f[u][0]=0,f[u][1]=val[u];    go(u)if(v!=fa){        dp(v,u),f[u][0]+=f[v][1],f[u][1]+=min(f[v][0],f[v][1]);    }}int main(){//  freopen("testdata.in","r",stdin);    w[0]=mul[0]=Matrix(1),n=read(),m=read(),getstr();    fp(i,1,n)val[i]=read();    for(R int i=1,u,v;i