题目大意：给一颗有点权的树，每次规定两个点选还是不选，求这棵树的最小权点覆盖。

题解

ZZ码农题。

要用动态dp做，这题就是板子，然鹅并不会，留坑代填。

因为没有修改，所以可以静态倍增。

我们先做一遍正常的树形dp，求出g[i][0/1]，0/1表示当前节点选或不选。

然后我们再倒腾出一个数组l[i][0/1]表示从当前点作为根，再扣掉当前子树的答案。

然后倍增处理dp[i][j][0/1][0/1]表示从i向上2ⁱ长度的链，起点和终点的选择情况，表示以下区域的答案。

 

比如这条黑色的链，它表示的是黄圈里的所有点的答案。

然后对于一个询问，我们可以跳LCA，边跳变统计答案，这样我们就可以统计出以LCA为根的子树的答案，在加上之前处理过的l数组的答案，就可以吧答案算全了。

NOIP考这种****题有意思吗？

代码

#include
     
      #include
      
       #define N 100009using namespace std;typedef long long ll;int tot,head[N],deep[N],p[N][20],n,m;char typef[5];ll dp[N][19][2][2],w[N],f[2][2],g[2][2],pr[N][2],lian[N][2],pr2[N][2];inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{
   int n,to;}e[N<<1];inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}inline void hb(int x,int y,int l){    dp[x][l][0][0]=min(dp[x][l-1][0][1]+dp[y][l-1][1][0],dp[x][l-1][0][0]+dp[y][l-1][0][0]);    dp[x][l][1][0]=min(dp[x][l-1][1][1]+dp[y][l-1][1][0],dp[x][l-1][1][0]+dp[y][l-1][0][0]);    dp[x][l][0][1]=min(dp[x][l-1][0][1]+dp[y][l-1][1][1],dp[x][l-1][0][0]+dp[y][l-1][0][1]);    dp[x][l][1][1]=min(dp[x][l-1][1][1]+dp[y][l-1][1][1],dp[x][l-1][1][0]+dp[y][l-1][0][1]);}void dfs(int u,int fa){    for(int i=1;(1<
       
        <=deep[u];++i){        p[u][i]=p[p[u][i-1]][i-1];        hb(u,p[u][i-1],i);    }    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){        int v=e[i].to;deep[v]=deep[u]+1;p[v][0]=u;        dp[v][0][0][1]=pr[u][1]-min(pr[v][1],pr[v][0]);        dp[v][0][1][0]=pr[u][0]-pr[v][1];        dp[v][0][1][1]=pr[u][1]-min(pr[v][1],pr[v][0]);        dfs(v,u);    }}void predfs(int u,int fa){    pr[u][0]=0;pr[u][1]=w[u];    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){        int v=e[i].to;predfs(v,u);        pr[u][0]+=pr[v][1];pr[u][1]+=min(pr[v][0],pr[v][1]);    }}void dfs2(int u,int fa){    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){        int v=e[i].to;    //    pr2[v][0]=pr2[u][1];pr2[v][1]=min(pr2[u][0],pr2[u][1]);    //    lian[v][0]=pr2[v][0]-pr[v][0];lian[v][1]=pr2[v][1]-pr[v][1];       lian[v][0]=lian[u][1]+pr[u][1]-min(pr[v][0],pr[v][1]);       lian[v][1]=min(lian[v][0],lian[u][0]+pr[u][0]-pr[v][1]);        dfs2(v,u);    }}inline ll getlca(int a,int b,int x,int y){    if(deep[a]
        
         =0;--i)if(deep[a]-(1<
         
          =deep[b]){        f[now][1]=min(f[pre][0]+dp[a][i][0][1],f[pre][1]+dp[a][i][1][1]);        f[now][0]=min(f[pre][0]+dp[a][i][0][0],f[pre][1]+dp[a][i][1][0]);        swap(now,pre);a=p[a][i];    }    if(a==b)return ans+f[pre][y]+lian[a][y];    g[pre][y]=0;ans+=pr[b][y];//cout<
          
           <
           
            =0;--i)if(p[a][i]!=p[b][i]){ f[now][1]=min(f[pre][0]+dp[a][i][0][1],f[pre][1]+dp[a][i][1][1]); f[now][0]=min(f[pre][0]+dp[a][i][0][0],f[pre][1]+dp[a][i][1][0]); g[now][1]=min(g[pre][0]+dp[b][i][0][1],g[pre][1]+dp[b][i][1][1]); g[now][0]=min(g[pre][0]+dp[b][i][0][0],g[pre][1]+dp[b][i][1][0]); swap(now,pre);a=p[a][i];b=p[b][i]; } swap(now,pre); ll ans1=f[now][1]+g[now][1]+pr[p[a][0]][0]-pr[a][1]-pr[b][1]; ll ans2=min(f[now][1],f[now][0])+min(g[now][0],g[now][1])+pr[p[a][0]][1]-min(pr[a][0],pr[a][1])-min(pr[b][0],pr[b][1]); return ans+min(ans1+lian[p[a][0]][0],ans2+lian[p[a][0]][1]);}int main(){ n=rd();m=rd();scanf("%s",typef);int u,v; for(int i=1;i<=n;++i)w[i]=rd(); for(int i=1;i<=n;++i) for(int j=0;j<=18;++j) for(int k=0;k<=1;++k)for(int l=0;l<=1;++l)dp[i][j][k][l]=1e12; for(int i=1;i
            
             1e10)puts("-1");else printf("%lld\n",ans); } return 0;}