邓亚萍近况 做网站败光20亿,app注册推广团队,洛阳青峰网络公司做网站,网站良精企业网站系统解析
题意描述令人一脸懵逼… 看了一下样例再回去看那个uninity的定义才大概明白#xff0c;题目所求的其实就是按照给出树构造的点分树的最大深度的最小值。
然后…就不会辣qwq 一开始的方向就错了#xff0c;尝试通过确定分治重心来考虑#xff0c;还真发现了一些挺有意…解析
题意描述令人一脸懵逼… 看了一下样例再回去看那个uninity的定义才大概明白题目所求的其实就是按照给出树构造的点分树的最大深度的最小值。
然后…就不会辣qwq 一开始的方向就错了尝试通过确定分治重心来考虑还真发现了一些挺有意思的性质然鹅并没有啥用…
一个关于点分树非常经典的等价转换给每个点赋一个权值作为深度那么赋值方案合法当且仅当 ∀depidepjx,∃k∈path(i,j),depkx\forall dep_idep_jx,\exists k\in path(i,j),dep_kx∀depidepjx,∃k∈path(i,j),depkx。 为了方便我们可以把深度取反这样最后的符号就反过来了比较好考虑。 然后从叶子往上贪心的确定每个节点的最小深度定义集合 banx{k∣dsonk,son∈subtree(x),∄y∈path(son,x),dyk}ban_{x}\{k|d_{son}k,son\in subtree(x),\not\exists y\in path(son,x),d_yk\}banx{k∣dsonk,son∈subtree(x),∃y∈path(son,x),dyk} 。 首先当前点x肯定不能填属于任意一个儿子ban集合的值同时如果存在两个儿子 x,yx,yx,y 使得它们的ban集合都有k那么x的取值就必须大于k。 由于答案是 O(logn)O(\log n)O(logn) 的模拟即可总复杂度 O(nlogn)O(n\log n)O(nlogn)。 使用 built_in 函数似乎可以做到线性
#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 double eps1e-10;
const int mod998244353;
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;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m,k;
int ban[N],f[N];
vectorinte[N];
int ans;
void dfs(int x,int fa){int s(0),t(0);for(int to:e[x]){if(tofa) continue;dfs(to,x);ban[x]|ban[to];t|(sban[to]);s|ban[to];}for(int i20;i0;i--){if(t(1i)) break;if((s(1i))0) f[x]i;}for(int i0;if[x];i){if(ban[x](1i)) ban[x]^(1i);}ban[x]|(1f[x]);ansmax(ans,f[x]);
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}dfs(1,0);printf(%d\n,ans);return 0;
}
