日常猝死。

　　A：f[i]表示子树内包含根且可以继续向上延伸的路径的最大价值，统计答案考虑合并两条路径即可。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 300010#define inf 10000000000000000llchar getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,p[N],t;ll f[N][2],a[N],ans;struct data{ int to,nxt,len;}edge[N<<1];void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}void dfs(int k,int from){ f[k][1]=f[k][0]=a[k]; ll mx=-inf,mx2=-inf; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { dfs(edge[i].to,k); ll x=f[edge[i].to][1]-edge[i].len; if (x>mx) mx2=mx,mx=x; else if (x>mx2) mx2=x; } f[k][1]=max(mx+a[k],a[k]); f[k][0]=max(f[k][0],f[k][1]); f[k][0]=max(f[k][0],a[k]+mx+mx2);}int main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i
           
          
         
        
       
      

　　B：每次一有还不错的开局马上就自闭了。一直都在正解附近徘徊愣是过了1h才pp。没救了。如果一个字符串最早在第i位与其他字符串都不同，其可以提供n-i+1的贡献。那么贪心的尽量让高位不同。问题在于如何统计贡献。将a看成0，b看成1后，变成两个二进制数。对于每一个前缀，将两个前缀二进制数相减得到的就是这段前缀的不同串数量。减去上一位的就可以得到在该位新出现的前缀个数。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 500010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],b[N];ll ans,tot,f[N],m;int main(){#ifndef ONLINE_JUDGE freopen("b.in","r",stdin); freopen("b.out","w",stdout);#endif n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=getc()-'a'; for (int i=1;i<=n;i++) b[i]=getc()-'a'; ll x=0,y=0; for (int i=1;i<=n;i++) { x=x<<1|a[i],y=y<<1|b[i]; f[i]=y-x+1; ans+=1ll*(min(m,f[i])-f[i-1])*(n-i+1); if (f[i]>m) break; } cout<
           
          
         
        
       
      

　　E：E过的人最多当然是看E了。冷静了一会发现排个序之后就成了一个序列问题，可以瞎dp了，式子写出来发现一发斜率优化就完了。然后我也不知道发生了啥。

　　按横坐标从小到大排序，那么如果选择了某个矩形，其后面的矩形产生的贡献就与前面的矩形无关了。于是有一发显然的dp，即设f[i]为选择第i个矩形时前i个矩形的最大价值，有f[i]=max{f[j]+(x_i-x_j)y_i-a_i}。式子是裸的不能再裸的斜率优化，就做完了。鬼知道发生了啥啊？

　　然后终测完了终于看到了第三个点是啥……woc a_i是可以爆int的啊？怎么想的到啊？以后干脆还是都define int long long算了反正cf机子不虚……心态爆炸。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define ll long long#define N 1000010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}ll read(){ ll x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,q[N];ll f[N];struct data{ int x,y;ll v; bool operator <(const data&a) const { return x
             
              a[i].y) head++; f[i]=f[q[head]]+t-1ll*a[q[head]].x*a[i].y; while (head
              
             
            
           
          
         
        
       
      

　　完全能翻的场还是莫名其妙就跪掉了，自闭。

　　result：rank 146 rating -3