南通seo网站价格,wordpress的模板文件,商城网站建站系统,seo的网站E. Dog Snacks
Heltion大佬题解 fuf_ufu表示节点uuu到最近叶子节点的距离。
首先不难发现#xff0c;考虑一棵子树根节点为uuu#xff0c;一定每次都把一整棵子树上的食物吃完#xff0c;然后再去别的子树。
由于每次狗总是先去离他最近的节点#xff0c;如果我们把一…E. Dog Snacks
Heltion大佬题解
fuf_ufu表示节点uuu到最近叶子节点的距离。
首先不难发现考虑一棵子树根节点为uuu一定每次都把一整棵子树上的食物吃完然后再去别的子树。
由于每次狗总是先去离他最近的节点如果我们把一棵子树的食物吃完时一定停留在一个叶子节点上即从叶子节点直接到另一棵子树。
然后就是结论 考虑每个非根非叶子结点,可以发现对其每个儿子vvv都要满足k≥fv2k≥f_v2k≥fv2. 对于根节点除至多一个儿子之外的每个儿子vvv都要满足k≥fv2k≥f_v2k≥fv2而那个儿子只需满足k≥ft1k≥f_t1k≥ft1不难发现我们需要让ftf_tft越大越好因为要么1要么2显然让最大的1才可能全局最可能小。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010,M2*N;
int h[N],e[M],ne[M],idx;
int n,res;
int f[N],dep[N],d[N];
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
void dfs(int u,int fa)
{vectorint w;for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;dfs(j,u);f[u]min(f[j]1,f[u]);w.push_back(f[j]);}if(w.empty()) return;// 计算答案sort(w.begin(),w.end());for(int i0;i1w.size();i) resmax(res,w[i]2);if(u1) resmax(res,w.back()1);else resmax(res,w.back()2);
}
int main()
{IO;int T1;cinT;while(T--){cinn;for(int i1;in;i) h[i]-1,f[i]n1,d[i]0;// 初始化idxres0;for(int i1;in;i){int a,b;cinab;add(a,b),add(b,a);d[a],d[b];}for(int i1;in;i)if(d[i]1) f[i]0;// 叶子dfs(1,-1);coutres\n;}return 0;
}
