建设网站协议,网站运营培训机构,老婆的视频在线观看1,网站 建设意见Foreword\text{Foreword}Foreword
《小清新》树形 dp。 其实本题没有那么#xff08;重读#xff09;恶心#xff0c;但我一开始写完 x0x0x0 后眼瞎没有看到 x1,2x1,2x1,2 时也必然是最优方案#xff08;这种东西不黑体吗…#xff09;可以直接无视#xff0c;还在苦苦的…Foreword\text{Foreword}Foreword
《小清新》树形 dp。 其实本题没有那么重读恶心但我一开始写完 x0x0x0 后眼瞎没有看到 x1,2x1,2x1,2 时也必然是最优方案这种东西不黑体吗…可以直接无视还在苦苦的写强制选链的特殊情况被狠狠的恶心到了。 这个故事告诉我们要仔细审题
感觉自己的做法还是挺舒服的虽然核心转移看的有些长也只有 40 行左右但没有太多的分类讨论和有些代码枚举儿子然后直接取十几行 max\maxmax 相比感觉更加阳间。
Solution\text{Solution}Solution
题意算比较简洁清晰了再具体一些大概就是选出两条可重点不可重边的链将树分割成尽可能多的连通块。
一开始我受 希望 那个题的影响尝试了好一会用度数和点数简洁的表示出连通块数目来简化 dp其实是在玩泥巴直接做就很方便。
Definition\text{Definition}Definition
设置状态 fx,i,df_{x,i,d}fx,i,d 表示 xxx 节点子树内选择了 iii 条已经确定的链子树内 的联通块最大数目。 ddd 的定义有些复杂 在 xxx 作为父亲的时候d∈[0,4]d\in [0,4]d∈[0,4] 表示的是 xxx 被删除与 xxx 相连的儿子的个数d5d5d5 表示 xxx 不被删除。 在 xxx 作为儿子的时候d∈[0,1]d\in [0,1]d∈[0,1] 表示 xxx 被删除且与父亲相连/不相连。d5d5d5 表示 xxx 不被删除。
Transfer\text{Transfer}Transfer
Part 1
d5d5d5xxx 不删时xxx 必然不会和儿子相连儿子要么删了但不和父亲连d0d0d0要么根本不删 (d5d5d5)不删的时候由于父子都不删两个联通块合并成一个所以答案要减一。 fx,i,5fson,j,5−1→fx,ij,5f_{x,i,5}f_{son,j,5}-1\to f_{x,ij,5}fx,i,5fson,j,5−1→fx,ij,5 fx,i,5fson,j,0→fx,ij,5f_{x,i,5}f_{son,j,0}\to f_{x,ij,5}fx,i,5fson,j,0→fx,ij,5 d∈[0,4]d\in[0,4]d∈[0,4] 时xxx 可以和儿子相连也可以不连不连的时候儿子是否删除都可以对应转移分别就是 fx,i,dfson,j,1→fx,ij,d1f_{x,i,d}f_{son,j,1}\to f_{x,ij,d1}fx,i,dfson,j,1→fx,ij,d1 fx,i,dfson,j,0→fx,ij,df_{x,i,d}f_{son,j,0}\to f_{x,ij,d}fx,i,dfson,j,0→fx,ij,d fx,i,dfson,j,5→fx,ij,df_{x,i,d}f_{son,j,5}\to f_{x,ij,d}fx,i,dfson,j,5→fx,ij,d 这样 xxx 从所有儿子得到的转移就全完事了接下来我们需要把 fx,i,df_{x,i,d}fx,i,d 的 ddd 的定义从“父亲形态”转化成“儿子形态”以使它可以继续向父亲转移。
Part 2
d5d5d5 时xxx 没选就是没选没什么好说的。 fx,i,5→fx,i,5f_{x,i,5}\to f_{x,i,5}fx,i,5→fx,i,5 d0d0d0 时注意我们之前是强制让 xxx 被删除的所以我们不能直接让它转移到 fx,i,0f_{x,i,0}fx,i,0。为了删除它要么使其单独一个点成链要么让它成为链尾和父亲相连对应就是 fx,i,0→fx,i1,0f_{x,i,0}\to f_{x,i1,0}fx,i,0→fx,i1,0 fx,i,0→fx,i,1f_{x,i,0}\to f_{x,i,1}fx,i,0→fx,i,1
d2/4d2/4d2/4 时向 xxx 连接的偶数条边必然两两成链 fx,i,d→fx,id/2,0f_{x,i,d}\to f_{x,id/2,0}fx,i,d→fx,id/2,0 d1/3d1/3d1/3 时单出来的一条可以把 xxx 当成链头停止也可以继续向父亲延伸 fx,i,d→fx,id/21,0f_{x,i,d}\to f_{x,id/21,0}fx,i,d→fx,id/21,0 fx,i,d→fx,id/2,1f_{x,i,d}\to f_{x,id/2,1}fx,i,d→fx,id/2,1
Part 3
这样看起来就做完了 但是你一测发现过不去样例 仔细一看是被两个点一条边的情况 hackhackhack 了。 一般的当一个图长成深度为 1 的菊花的时候我们都会出问题。 我们缺少了在一个点连续摆烂的情况。 这个东西有两种解决方案 第一种是当 xxx 被删除的时候可以原地多选几条链即 fx,i,0→fx,i1,0f_{x,i,0}\to f_{x,i1,0}fx,i,0→fx,i1,0 fx,i,1→fx,i1,1f_{x,i,1}\to f_{x,i1,1}fx,i,1→fx,i1,1 第二种是求出度数最大点的度数让答案和这个度数取个 max\maxmax。 第二种虽然看起来更加简单跑起来也稍微快一点但如果在考场上本人还是建议第一种毕竟多说多错直接给一个合法转移让 std::max 做决策而不是自己归纳贪心肯定更加稳妥。 如果是做练习当然就精益求精啦。
Code\text{Code}Code
代码就简单了把上面的转移敲出来即可。 滚动数组无脑好用不会互相转移出 bug强推
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N1e5100;
const int M2e5100;
const int inf1e9;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n;
int f[N][3][6];
int tmp[2][3][6],now,pre;
vectorintv[N];
inline void Max(int x,int y){yx?xy:0;return;
}
void dfs(int x,int fa){for(int to:v[x]){if(tofa||vis[to]) continue;dfs(to,x);}now1;pre0;memset(tmp,-0x3f,sizeof(tmp));tmp[now][0][5]1;tmp[now][0][0]0;for(int s:v[x]){if(sfa||vis[s]) continue;swap(now,pre);memset(tmp[now],-0x3f,sizeof(tmp[now]));for(int i0;i2;i){for(int j0;ij2;j){Max(tmp[now][ij][5],tmp[pre][i][5]f[s][j][5]-1);Max(tmp[now][ij][5],tmp[pre][i][5]f[s][j][0]);for(int d0;d4;d){Max(tmp[now][ij][d],tmp[pre][i][d]f[s][j][0]);Max(tmp[now][ij][d],tmp[pre][i][d]f[s][j][5]);if(d14)Max(tmp[now][ij][d1],tmp[pre][i][d]f[s][j][1]);}} }}memset(f[x],-0x3f,sizeof(f[x]));for(int i0;i2;i){Max(f[x][i][5],tmp[now][i][5]);if(i12) Max(f[x][i1][0],tmp[now][i][0]);Max(f[x][i][1],tmp[now][i][0]);for(int j1;j4;j){if(j1){if(ij/22) Max(f[x][ij/2][1],tmp[now][i][j]);if(i(j1)/22) Max(f[x][i(j1)/2][0],tmp[now][i][j]);}else if(ij/22) Max(f[x][ij/2][0],tmp[now][i][j]);}}for(int i1;i2;i){Max(f[x][i][0],f[x][i-1][0]);Max(f[x][i][1],f[x][i-1][1]);}return;
}
void work0(){for(int i1;in;i){int xread(),yread();v[x].push_back(y);v[y].push_back(x);}dfs(1,0);printf(%d\n,max(f[1][2][0],f[1][2][5]));return;
}
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifint Tread(),opread();while(T--){nread();for(int i1;iop;i) read(),read();work0();for(int i1;in;i) v[i].clear();}return 0;
}
/*
*/
