【SHOISXOI2017】bzoj4871 摧毁“树状图”_综合

考虑关于边的树形dp，对于有向边 $e:u->v$ ，维护

f e = max {d e g v ? 1, f e 1 + deg v ? 2} (e 1 : v ? > w, w \neq u) g e = max {f e, f e 1 + f e 2 + deg v ? 3} (e 1 : v ? > w, e 2 : v ? > x, w, x, u 互 不 相 等) h e = max {g e, h e 1} (e 1 : v ? > w, w \neq u)

$f_e=\max\{deg_v-1,f_{e1}+\deg_v-2\} (e1:v->w,w\ne u) \\ g_e=\max\{f_e,f_{e1}+f_{e2}+\deg_v-3\} (e1:v->w,e2:v->x,w,x,u\text{互不相等})\\ h_e=\max\{g_e,h_{e1}\}(e1:v->w,w\ne u) \\$
分别表示从

v $v$ 往下走得到的最多连通块，从下面上到

v $v$ 再下去得到的最多连通块，

v $v$ 的子树可能得到的最多连通块。注意，这里的连通块个数都不计算

u $u$ 所在的连通块。
具体求解可以采用记忆化搜索。
一条路径的情况，可以用

he+1 $h_e+1$ 更新答案。
接下来考虑两条路径的情况。
如果两条路径不相交，可以更新答案的有

h e 1 + h e 2 (e 1 : u ? > v, e 2 : v ? > u) h e 1 + h e 2 + 1 (e 1 : u ? > v, e 2 : u ? > w, v \neq w)

$h_{e1}+h_{e2}(e1:u->v,e2:v->u) \\ h_{e1}+h_{e2}+1 (e1:u->v,e2:u->w,v\ne w) \\$
如果两条路径在某点相交，可以更新答案的有

f e 1 + f e 2 + f e 3 + deg u ? 3 (e 1 : u ? > v, e 2 : u ? > w, e 3 : u ? > x, v, w, x 互 不 相 等) f e 1 + f e 2 + f e 3 + f e 4 + deg u ? 4 (e 1 : u ? > v, e 2 : u ? > w, e 3 : u ? > x, e 4 : u ? > y, v, w, x, y 互 不 相 等)

$f_{e1}+f_{e2}+f_{e3}+\deg_u-3(e1:u->v,e2:u->w,e3:u->x,v,w,x\text{互不相等}) \\ f_{e1}+f_{e2}+f_{e3}+f_{e4}+\deg_u-4(e1:u->v,e2:u->w,e3:u->x,e4:u->y,v,w,x,y\text{互不相等}) \\$

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200010,oo=100000000;
int fir[maxn],ne[maxn],to[maxn],deg[maxn],
f[maxn],g[maxn],h[maxn],vis[maxn],
n,X;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
void add(int num,int u,int v)
{ne[num]=fir[u];fir[u]=num;to[num]=v;
}
void dp(int e)
{if (vis[e]) return;int u=to[e],f1=-oo,f2=-oo;vis[e]=1;h[e]=-oo;for (int i=fir[to[e]];i;i=ne[i])if (i!=(e^1)){dp(i);h[e]=max(h[e],g[i]);if (f[i]>=f1){f2=f1;f1=f[i];}else f2=max(f2,f[i]);}f[e]=max(deg[u]-1,f1+deg[u]-2);g[e]=max(f[e],f1+f2+deg[u]-3);h[e]=max(h[e],g[e]);
}
void solve()
{int u,v,f1,f2,f3,f4,h1,h2,ans=0;n=rd();if (X) rd(),rd();if (X==2) rd(),rd();for (int i=1;i<=n;i++) fir[i]=deg[i]=0;for (int i=1;i<n;i++){u=rd();v=rd();deg[u]++;deg[v]++;add(i<<1,u,v);add(i<<1|1,v,u);vis[i<<1]=vis[i<<1|1]=0;}for (int i=1;i<=n;i++){f1=f2=f3=f4=h1=h2=-oo;for (int j=fir[i];j;j=ne[j]){dp(j);ans=max(ans,h[j]+1);if (vis[j^1]) ans=max(ans,h[j]+h[j^1]);if (f[j]>=f1){f4=f3;f3=f2;f2=f1;f1=f[j];}else{if (f[j]>=f2){f4=f3;f3=f2;f2=f[j];}else{if (f[j]>=f3){f4=f3;f3=f[j];}else f4=max(f4,f[j]);}}if (h[j]>=h1){h2=h1;h1=h[j];}else h2=max(h2,h[j]);}ans=max(ans,h1+h2+1);ans=max(ans,f1+f2+f3+deg[i]-3);ans=max(ans,f1+f2+f3+f4+deg[i]-4);}printf("%d\n",ans);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;T=rd();X=rd();while (T--) solve();
}