题解：

一道优秀的题目

有几种做法：

1.维护后缀和

刚开始我想的是维护前缀和

然后用$sum[x]-sum[y]>=dep[x]-dep[y]$来做

但是这样子树赋值为0这个操作就很难进行了

因为你查找的是链上最小值，所以不改子树上面的节点是做不了的

那我们换一种方式，单点改，查询区间最大后缀和

这样子树染白的时候我们就可以在x处减去一个上面的最大后缀和，那么就对子树没有影响了

然后再把子树清空一下就可以

其实这个东西就是动态dp。。。

$$f(v)=max(f(x)-1,0)+v[v]$$

这个只用查询链

所以我们只需要维护$f[v]=MAX(f[top]必选时的最大值k1,任意情况最大值k2)$就可以了(v都是必选点）

 

#include 
     
      using namespace std;#define rint register int#define IL inline#define rep(i,h,t) for(int i=h;i<=t;i++)#define dep(i,t,h) for(int i=t;i>=h;i--)#define ll long long#define me(x) memset(x,0,sizeof(x))#define mep(x,y) memcpy(x,y,sizeof(y))#define mid ((h+t)>>1)namespace IO{    char ss[1<<24],*A=ss,*B=ss;    IL char gc()    {        return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;    }    template
      
        void read(T &x)    {        rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);        while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;     }    char sr[1<<24],z[20]; ll Z,C1=-1;    template
       
        void wer(T x)    {        if (x<0) sr[++C1]='-',x=-x;        while (z[++Z]=x%10+48,x/=10);        while (sr[++C1]=z[Z],--Z);    }    IL void wer1()    {        sr[++C1]=' ';    }    IL void wer2()    {        sr[++C1]='\n';    }    template
        
         IL void maxa(T &x,T y) {
   if (x
         
          IL void mina(T &x,T y) {
   if (x>y) x=y;}     template
          
           IL T MAX(T x,T y){ return x>y?x:y;} template
           
            IL T MIN(T x,T y){ return x
            
             =0) cout<<"black"<
            
           
          
         
        
       
      
     

 

 

 

2.操作分块

分块这个东西有的时候的确简单巧妙。。

但一般我也不会去想分块。。

这个是看了别人题解的。。

我们以每$\sqrt{n}$个元素分一组

对块内的操作，我们等待$\sqrt{n}$都做完了再把这$\sqrt{n}$个操作加入树中

对于当前的询问，我们只需要树内的$\sqrt{n}$个节点的信息就可以了

我们可以建立虚树维护

本来打算学树上分块的。。。但发现这东西并没有啥用

会线段树合并/dsu on tree/树上莫队 应该不会也没啥关系

像这种利用虚树的题目还是比较多的