新余做网站,常州网站推广软件,免费手机app制作,郑州市东区建设环保局官方网站解析
神仙题 关键在于找到一个满足题意的充要条件
结论#xff1a;所有的合法答案一定是由树上一条链及其相邻的点组成的独立集
充分性比较显然#xff0c;这个东西随便画画就可以构造出合法的解来 所以我们只要考虑必要性 考虑不满足这个结论的方案 可以“发现”它一定是…解析
神仙题 关键在于找到一个满足题意的充要条件
结论所有的合法答案一定是由树上一条链及其相邻的点组成的独立集
充分性比较显然这个东西随便画画就可以构造出合法的解来 所以我们只要考虑必要性 考虑不满足这个结论的方案 可以“发现”它一定是无解的 为什么 懒得写了 这篇博客已经“发现”的很明白了
转化完题意后的dp就比较简单了
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
ll read() {ll x0,f1;char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {xx*10(c^48);cgetchar();}return x*f;
}
inline void Max(int x,int y){if(xy) xy;}
int n,m;
struct edge{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](edge){y,fi[x]};fi[x]cnt;return;
}
int dp[N][2],du[N];
int ans(0);
void dfs(int x,int f){//dp[x][0]du[x]-1;dp[x][1]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs(to,x);Max(ans,dp[x][0]max(dp[to][0],dp[to][1]));Max(ans,dp[x][1]dp[to][0]);Max(dp[x][0],max(dp[to][1],dp[to][0])du[x]-2);Max(dp[x][1],dp[to][0]1);}//Max(dp[x][0],du[x]-1);Max(ans,max(dp[x][0],dp[x][1]));return;
}
int main() {
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();for(int i1;in;i){int xread(),yread();du[x];du[y];addline(x,y);addline(y,x);}dfs(1,0);printf(%d\n,ans);return 0;
}
