本来今天想学基环树的

认真看一看，这不就是弱化的仙人掌嘛

然后，就直接仙人掌上DP咯（蒟蒻不是很会调了一晚上。。。）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;struct node{ int x,y,next;}a[2100000];int len,last[1100000];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}LL ft[1100000],f[2][1100000];int z,dfn[1100000],fa[1100000];bool v[1100000];//是否在仙人掌中void DP(int rt,int x)//只需要更新rt { LL g[2][2]; int pre=0,now=1; g[now][0]=g[now][1]=0; for(int i=x;i!=rt;i=fa[i]) { swap(pre,now); g[now][0]=max(g[pre][0],g[pre][1])+f[0][i]; g[now][1]=g[pre][0]+f[1][i]; } f[0][rt]+=max(g[now][0],g[now][1]); //不取rt pre=0,now=1; g[now][0]=g[now][1]=0; for(int i=x;i!=rt;i=fa[i]) { swap(pre,now); g[now][0]=max(g[pre][0],g[pre][1])+f[0][i]; if(i==x||fa[i]==rt)g[now][1]=0; else g[now][1]=g[pre][0]+f[1][i]; } f[1][rt]+=max(g[now][0],g[now][1]); //取rt }int h[1100000];void cactus(int x){ dfn[x]=++z; f[0][x]=0;f[1][x]=ft[x]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(dfn[y]==0) fa[y]=x, cactus(y); } for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(fa[x]!=y) { if(dfn[y]