去年noip题啊...
这题动态dp裸题,因此直接套上去嘛!
动态dp板子看这里
设状态$f[i][0/1]$表示点$i$选/不选的最小花费,转移有
$f[i][0]=sum f[son][1]$
$f[i][1]=w_{i}+sum min(f[son][0],f[son][1])$
同样设一个$g[i][0/1]$表示$f$去掉重儿子的贡献,也就是:
$f[i][0]=f[Son][1]+g[i][0]$
$f[i][1]=min(f[Son][1],f[Son][0])+g[i][1]$
化成最小值的形式:
$f[i][0]=min(f[Son][1]+g[i][0],infty)$
$f[i][1]=min(f[Son][1]+g[i][1],f[Son][0]+g[i][1])$
然后写成矩阵的形式:
$egin{pmatrix}f[i][1] \f[i][0]end{pmatrix}$ $=$ $egin{pmatrix} g[i][1] & g[i][1] \ g[i][0]& infty end{pmatrix}$ $egin{pmatrix} f[son_{i}][1]\f[son_{i}][0] end{pmatrix}$
然后同样线段树维护即可
贴代码:
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <map> #define ll long long #define rt1 rt<<1 #define rt2 (rt<<1)|1 using namespace std; const ll inf=0x3f3f3f3fll; char whatever[50]; struct MAT { ll a[2][2]; friend MAT operator * (MAT x,MAT y) { MAT ret; ret.a[0][0]=min(x.a[0][0]+y.a[0][0],x.a[0][1]+y.a[1][0]); ret.a[0][1]=min(x.a[0][1]+y.a[1][1],x.a[0][0]+y.a[0][1]); ret.a[1][0]=min(x.a[1][0]+y.a[0][0],x.a[1][1]+y.a[1][0]); ret.a[1][1]=min(x.a[1][1]+y.a[1][1],x.a[1][0]+y.a[0][1]); return ret; } }ori[100005]; MAT tree[400005]; map <int,int> M[100005]; vector <int> v[100005]; int inr[100005]; ll w[100005]; int siz[100005],ed[100005],ttop[100005],f[100005],son[100005],nnum[100005],dep[100005],onum[100005]; ll F[100005][2]; int n,m,tot; ll S=0; void dfs(int x,int fx) { f[x]=fx,dep[x]=dep[fx]+1,siz[x]=1; for(int i=0;i<v[x].size();i++) { int to=v[x][i]; if(to==fx)continue; dfs(to,x); siz[x]+=siz[to],son[x]=(siz[to]>siz[son[x]])?to:son[x]; } } void redfs(int x,int fx,int topx) { ttop[x]=topx,nnum[x]=++tot,onum[tot]=x; if(son[x])redfs(son[x],x,topx),ed[x]=ed[son[x]]; else ed[x]=x; for(int i=0;i<v[x].size();i++) { int to=v[x][i]; if(to==fx||to==son[x])continue; redfs(to,x,to); } } void tree_dp(int x,int fx) { F[x][1]=w[x]; for(int i=0;i<v[x].size();i++) { int to=v[x][i]; if(to==fx)continue; tree_dp(to,x); F[x][0]+=F[to][1],F[x][1]+=min(F[to][1],F[to][0]); } } void buildtree(int rt,int l,int r) { if(l==r) { int x=onum[l]; ll g0=F[x][0]-F[son[x]][1],g1=F[x][1]-min(F[son[x]][0],F[son[x]][1]); ori[x].a[0][0]=ori[x].a[0][1]=g1,ori[x].a[1][0]=g0,ori[x].a[1][1]=inf; tree[rt]=ori[x]; return; } int mid=(l+r)>>1; buildtree(rt1,l,mid),buildtree(rt2,mid+1,r); tree[rt]=tree[rt1]*tree[rt2]; } void update(int rt,int l,int r,int posi) { if(l==r){tree[rt]=ori[onum[posi]];return;} int mid=(l+r)>>1; if(posi<=mid)update(rt1,l,mid,posi); else update(rt2,mid+1,r,posi); tree[rt]=tree[rt1]*tree[rt2]; } MAT query(int rt,int l,int r,int lq,int rq) { if(l>=lq&&r<=rq)return tree[rt]; int mid=(l+r)>>1; if(rq<=mid)return query(rt1,l,mid,lq,rq); else if(lq>mid)return query(rt2,mid+1,r,lq,rq); else return query(rt1,l,mid,lq,rq)*query(rt2,mid+1,r,lq,rq); } void ins(int p,ll t) { ori[p].a[0][0]+=t-w[p],ori[p].a[0][1]=ori[p].a[0][0],w[p]=t; while(p) { MAT m0=query(1,1,n,nnum[ttop[p]],nnum[ed[p]]); update(1,1,n,nnum[p]); MAT m1=query(1,1,n,nnum[ttop[p]],nnum[ed[p]]); p=f[ttop[p]]; if(!p)break; ori[p].a[0][0]+=min(m1.a[0][0],m1.a[1][0])-min(m0.a[0][0],m0.a[1][0]); ori[p].a[0][1]=ori[p].a[0][0]; ori[p].a[1][0]+=m1.a[0][0]-m0.a[0][0]; } } template <typename T>inline void read(T &x) { T f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x=c*f; } int main() { read(n),read(m),scanf("%s",whatever); for(int i=1;i<=n;i++)read(w[i]),S+=w[i]; for(int i=1;i<n;i++) { int x,y; read(x),read(y); M[x][y]=M[y][x]=1; inr[x]++,inr[y]++; v[x].push_back(y),v[y].push_back(x); } dfs(1,0),redfs(1,0,1),tree_dp(1,1),buildtree(1,1,n); MAT ret=query(1,1,n,nnum[1],nnum[ed[1]]); while(m--) { int p1,typ1,p2,typ2; read(p1),read(typ1),read(p2),read(typ2); if(M[p1][p2])if(!typ1&&!typ2){printf("-1 ");continue;} ll temp1=w[p1],temp2=w[p2]; if(typ1)ins(p1,-inf); else ins(p1,inf); if(typ2)ins(p2,-inf); else ins(p2,inf); MAT ret=query(1,1,n,nnum[1],nnum[ed[1]]); ll delt=typ1*(inf+temp1)+typ2*(inf+temp2); printf("%lld ",min(ret.a[0][0],ret.a[1][0])+delt); ins(p1,temp1),ins(p2,temp2); } return 0; }