T1

每次都会发现。当你确定了这一步之后，下一步一定是确认的他一定有左右的方案交替组成。

代码

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+5,mod=1e9+7;
int n,k;
int a[maxn];
signed main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>k;a[0]=1;for(int i=1;i

T2

会发现最终的连出来的链除了两端的节点。其他的都会在原来的度数情况下少两个。那么此时我们只需要将所有的都减2，最后加2即可。

那么我们接下来的目标就是维护一个类似于直径的度数的情况。显然可以直接按照直径的方法来做

代码

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
vector g[maxn];
int f[maxn],ans=0,n;
void dfs(int u,int fa)
{int sz=g[u].size(),ft=-inf,sd=-inf;f[u]=sz;for(int v:g[u])if(v!=fa){dfs(v,u);f[u]=max(f[u],f[v]-2+sz);if(f[v]>ft)sd=ft,ft=f[v];else if(f[v]>sd)sd=f[v];}ans=max(ans,f[u]);if(ft!=inf&&sd!=inf)ans=max(ans,ft+sd+sz-4);
}
signed main()
{freopen("route.in","r",stdin);freopen("route.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);cout<

T3

其实如果说你如果强行dp的话，插头dp或者是状压dp都是个不错的选择

但我们只需要标记所有初始不能放点的地方合法的地方，就只需要要求不相邻就行了。

也就是求二分图的最大独立集。直接跑二分图匹配然后用总个数去减即可。

代码

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
int n,m,ans,cnt,cnt2,match[6405],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
bool st[6405],noo[85][85];
vector g[6405];
char mp[85][85];
bool find(int x)
{for(int u:g[x])if(!st[u]){st[u]=1;if(!match[u]||find(match[u])){match[u]=x;return 1;}}return 0;
}
int get(int x,int y)
{return (x-1)*m+y;
}
signed main()
{freopen("exam.in","r",stdin);freopen("exam.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(mp[i][j]=='1') noo[i][j]=1;if(mp[i][j]=='2'){noo[i][j]=1;cnt2++;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=1&&x<=n&&y>=1&&y<=m&&!noo[x][y]) noo[x][y]=1;}}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!noo[i][j])cnt++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!noo[i][j])for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=1&&x<=n&&y>=1&&y<=m&&!noo[x][y]) g[get(i,j)].push_back(get(x,y));}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!((i+j)&1)){memset(st,0,sizeof(st));if(find(get(i,j))) ans++;}cout<

T4

这种问题一般都是二分。那么边就会有大于等于二分值的或者小于等于二分值的

那么，先手在一或者后手在0，他们都一定就结束了。剩下的要看其他的点。

那么这里的话，你可以用一个队列去维护。从0度的点开始往前推。

代码

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
int n,m,ans,cnt,cnt2,match[6405],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
bool st[6405],noo[85][85];
vector g[6405];
char mp[85][85];
bool find(int x)
{for(int u:g[x])if(!st[u]){st[u]=1;if(!match[u]||find(match[u])){match[u]=x;return 1;}}return 0;
}
int get(int x,int y)
{return (x-1)*m+y;
}
signed main()
{freopen("exam.in","r",stdin);freopen("exam.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(mp[i][j]=='1') noo[i][j]=1;if(mp[i][j]=='2'){noo[i][j]=1;cnt2++;for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=1&&x<=n&&y>=1&&y<=m&&!noo[x][y]) noo[x][y]=1;}}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!noo[i][j])cnt++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!noo[i][j])for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=1&&x<=n&&y>=1&&y<=m&&!noo[x][y]) g[get(i,j)].push_back(get(x,y));}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!((i+j)&1)){memset(st,0,sizeof(st));if(find(get(i,j))) ans++;}cout<