2 条题解
-
0
by_lym（非正解，但代码最短，思路最简单，求hack）
#include<bits/stdc++.h> #define int long long //可以前往洛谷看tom_l的题解 using namespace std; const int N=5e4+5; int n; vector<pair<int,int> >f[N]; int mn[N]; void work(vector<pair<int,int> >&p){ sort(p.begin(),p.end()); vector<pair<int,int> >tmp; for(auto i:p){ if(tmp.empty()||i.second+i.first*i.first<tmp.back().second+tmp.back().first*tmp.back().first)tmp.push_back(i); } p=tmp; } vector<int>e[N]; struct node{ int first,second,id; }; void dfs(int x,int fa){ for(int y:e[x]){ if(y==fa)continue; dfs(y,x); } int res=0; for(int y:e[x]){ if(y==fa)continue; mn[y]=1e18; for(auto i:f[y]){ int l=i.first,s=i.second; l++; mn[y]=min(s+l*l,mn[y]); } res+=mn[y]; } for(int y:e[x]){ if(y==fa)continue; for(auto i:f[y]){ int l=i.first,s=i.second; f[x].emplace_back(l+1,s+i.second); } } int ad=1e18; unordered_map<int,unordered_map<unsigned long long,unordered_map<long long,int> > >mp; vector<node >tmp; for(int y:e[x]){ for(auto i:f[y]){ mp[i.first][i.second][mn[y]]++; if(mp[i.first][i.second][mn[y]]<=2)tmp.push_back({i.first,i.second,y}); } } for(auto i:tmp){ for(auto j:tmp){ if(i.id==j.id)continue; int tres=res-mn[i.id]-mn[j.id]; ad=min(ad,tres+i.second+j.second+(i.first+j.first+2)*(i.first+j.first+2)); } } f[x].emplace_back(0, ad ); if(e[x].size()==1){ if(e[x][0]==fa){ f[x].emplace_back(0,0); } else { for(auto i:f[e[x][0]]){ f[x].emplace_back(0,i.second+(i.first+1)*(i.first+1)); } } } for(int y:e[x]){ if(y!=fa){ f[y].clear(); f[y].shrink_to_fit(); } } work(f[x]); } signed main (){ cin>>n; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; e[x].push_back(y); e[y].push_back(x); } dfs(1,0); if(f[1].empty()){ cout<<"E"; exit(0); } cout<<f[1][0].second; return 0; }by hansang:
#include<bits/stdc++.h> //by: hansang using namespace std; typedef long long LL; const int N=5e4+10; const LL inf=1e9; LL dep[N], dp[N]; int n, p[N]; //dp[i]为i子树的最小成本但缺少切割线有关的部分值（看calc函数和主函数注释），p数组表示偏移（启发式） struct node{ LL d, c, f; //层数，当前点切割线有关花费，特殊值（后面会解释） bool tag; //0表示切割线竖穿当前点（连接父节点和子节点），1表示切割线横穿当前点（连接两个子节点） }; vector<int> G[N]; set<node> b[N]; bool operator<(node a, node b) { if(a.tag || b.tag) return (a.f<b.f); //结合主函数的注释理解 if(a.d!=b.d) return (a.d>b.d); //非查找情况下 return (a.c<b.c); } LL sqe(LL x) {return x*x;} LL calc(node n1, node n2){ //这个函数是求出特殊值f（可以理解为斜率，那我们维护的就是一个下凸壳） if(n1.d>n2.d) swap(n1, n2); //这个函数面向dep较小的，联系79，100和127行自行理解 LL res=(sqe(n1.d)+n1.c-sqe(n2.d)-n2.c)/(2*(n2.d-n1.d)); //L^2+2*L*l+(l^2+c)，目前只有l和c确定，那么就先计算2*L*l+(l^2+c) //当前我们有2*L*l1+(l1^2+c1)和2*L*l2+(l2^2+c2) //相减得到：(l1^2+c1)-(l2^2+c2)+2*L*l1-2*L*l2 (一种符号) 0 //化一下： l1^2+c1-l2^2-c2 (一种符号) -2*(l1-L2)*L //将-2*(l1-L2)除过去(不用变号)，就有：(l1^2+c1-l2^2-c2)/(2*(l2-L1)(一种符号)L //当(一种符号)为大于号时，代表着2*L*l1+(l1^2+c1)>2*L*l2+(l2^2+c2) //而我们要改变L直到(一种符号)为小于或等于号，这样n1才比n2优 //就像这样：(l1^2+c1-l2^2-c2)/(2*(l2-L1)>L，只要不断给 L+1，总会变号的 while((sqe(n1.d)+n1.c-sqe(n2.d)-n2.c)>res*2*(n2.d-n1.d)) res++; //实际上，L(f)就代表着该节点较优时，子树外切割线的最小值，所以上面才按f排序 return res; } void dfs(int x, int fa) { LL res=-1, sum=0; //成本最小的切割线的目前x子树成本，不含切割线的目前x子树成本 for(auto y: G[x]) if(y!=fa){ dep[y]=dep[x]+1; dfs(y, x); auto n1=*(--b[p[y]].upper_bound({0, 0, -dep[x], 1})); //f查找x就代表着要查找子树外切割线为x的最优解 //如果n1的f!=dep[x]，那么t就会大一点 LL t=sqe(n1.d-dep[x])+n1.c+dp[y]; //由y的切割线延申到x if(res!=-1) res+=t; //如果y不是第一个子节点，就累计 if(b[p[x]].empty()){ //启发式，如果x没有切割线 swap(p[x], p[y]); dp[x]=dp[y]; //dp[y]=0; //到时候取答案会直接取x，dp[y]不重要 } else{ LL os=dp[x]+t, ot=dp[y]+sum; //分别为切割线在y上x的最小成本，切割线不在y上x的最小成本 if(b[p[x]].size()<b[p[y]].size()){ //启发式，如果y的切割线比x的多话 swap(p[x], p[y]); swap(os, ot); //不改dp的原因是os和ot后面会赋值dp } for(auto it: b[p[y]]){ //合并两条边 auto n2=*(--b[p[x]].upper_bound({0, 0, it.d-2*dep[x], 1})); //见39行 LL tmp=sqe(it.d+n2.d-2*dep[x])+it.c+n2.c+dp[x]+dp[y]; //把x的切割线和y的切割线连在一起 if(res==-1 || tmp<res) res=tmp; //找到了成本更小的切割线，更新 } for(auto it: b[p[y]]){ it.c+=ot-os; //加上差值，代表当前情况切割线变到x其它不变（感性理解 auto n2=b[p[x]].insert(it).first; //这里first代表着插入it之后it在set里的位置 bool flag=0; //当前解是否最深 while(n2!=b[p[x]].begin()){ //不是最深的（维护it前的下凸壳） auto n3=n2; n3--; if((*n3).d==it.d){ //有层数和当前一样的解还更优 b[p[x]].erase(n2); //删除当前解 flag=1; break; } node no=*n3; it.f=calc(no, it); //赋值 b[p[x]].erase(n2); n2=b[p[x]].insert(it).first; //这里first代表着插入it之后it在set里的位置 if(it.f<=(*n3).f) b[p[x]].erase(n3); //维护下凸壳 else break; } if(flag) continue; if(n2==b[p[x]].begin()){ //当前最深解 it.f=-inf; //第一个的特殊值为无穷小 b[p[x]].erase(n2); n2=b[p[x]].insert(it).first; } auto n3=n2; n3++; while(n3!=b[p[x]].end()){ //维护it后的下凸壳 if(it.d==(*n3).d){ //同上 b[p[x]].erase(n3); n3=n2; n3++; continue; } node no=*n3; no.f=calc(it, no); if(no.f<=it.f){ b[p[x]].erase(n2); break; } b[p[x]].erase(n3); n3=b[p[x]].insert(no).first; auto n4=n3; n4++; if(n4!=b[p[x]].end() && (*n4).f<=no.f) { b[p[x]].erase(n3); n3=n4; } else break; } } dp[x]=os; //更新（加上y的贡献） } sum+=t; } if(b[p[x]].empty()){ //没有切割线或叶子节点 b[p[x]].insert({dep[x], 0, -inf, 0}); //见88行 } else if(res!=-1){ //之前x有切割线（其实还是维护下凸壳） node tmp={dep[x], res-dp[x], 0, 0}; //res-dp[x]为x点最优切割线有关花费 while(!b[p[x]].empty()){ node n1=*b[p[x]].rbegin(); tmp.f=calc(n1, tmp); if(tmp.f>n1.f) break; else b[p[x]].erase(n1); //tmp更优 } if(b[p[x]].empty()) tmp.f=-inf; //同88行 b[p[x]].insert(tmp); //插入 } } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) p[i]=i; //偏移值初始化 for(int i=1; i<n; i++){ int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } dep[1]=0; dfs(1, 0); auto it=b[p[1]].rbegin(); //取最后一个最靠近1的，含信息量高且因为维护过是最优的 printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); //1除切割线外花费+某点切割线花费+1到某点距离的平方 /* //其实原解是这样写的 if(G[1].size()==1){ auto it=--b[p[1]].upper_bound({0, 0, 0, 0}); printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); } else{ auto it=b[p[1]].rbegin(); printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); } //但我们发现第一种情况时，b[p[1]]里的f全都是负的 //upper_bound会返回end，所以两种情况可以合并 */ return 0; }原题解：
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct poss { LL depth, cost, takeover; bool tcheck; }; bool operator<(poss a, poss b) { if (a.tcheck || b.tcheck) return (a.takeover < b.takeover); if(a.depth!=b.depth) return (a.depth > b.depth); return (a.cost < b.cost); } const int N=5e4+10; int n; vector<int> edges[N]; bool visited[N]; long long depth[N]; long long offset[N]; set<poss>* best[N]; void recurse(int node) { visited[node] = true; LL bestPair = -1; LL allSoFar = 0; for (int i = 0; i < edges[node].size(); i++) { if (visited[edges[node][i]]) continue; depth[edges[node][i]] = depth[node]+1; recurse(edges[node][i]); LL tadd; { poss when = {0, 0, -depth[node], true}; set<poss>::iterator which = best[edges[node][i]]->upper_bound(when); which--; tadd = (depth[node]-which->depth)*(depth[node]-which->depth)+which->cost+offset[edges[node][i]]; } if (bestPair != -1) bestPair += tadd; if (best[node] == NULL) { best[node] = best[edges[node][i]]; offset[node] = offset[edges[node][i]]; } else { set<poss>* s = best[node], * t = best[edges[node][i]]; LL os = offset[node]+tadd, ot = offset[edges[node][i]]+allSoFar; //os:切割线在y上时x的成本; ot:切割线不在y上时x的成本 if (s->size() < t->size()) { //启发式合并，小的合并到大的 set<poss>* tem = s; s = t; t = tem; int to = os; os = ot; ot = to; } for (set<poss>::iterator it = t->begin(); it != t->end(); it++) { poss when = {0, 0, it->depth-2*depth[node], true}; set<poss>::iterator which = s->upper_bound(when); which--; LL thisPair = (it->depth+which->depth-2*depth[node])*(it->depth+which->depth-2*depth[node])+it->cost+which->cost+offset[node]+offset[edges[node][i]]; if (bestPair == -1 || thisPair < bestPair) bestPair = thisPair; } for (set<poss>::iterator it = t->begin(); it != t->end(); it++) { poss p = *it; p.cost += ot - os; //调整成本，使其对应x的情况 set<poss>::iterator where = s->insert(p).first; bool killed = false; while (where != s->begin()) { set<poss>::iterator prev = where; prev--; if (prev->depth == where->depth) { //相同深度的只保留成本最小的 s->erase(where); killed = true; break; } //计算两个节点的takeover，即当L取何值时两个节点的成本相等 p.takeover = (where->cost - prev->cost + where->depth*where->depth - -
0
huangzheng
LV 6
@ 2025-10-8 17:00:42
by_lym（非正解，但代码最短，思路最简单，求hack）
#include<bits/stdc++.h> #define int long long //可以前往洛谷看tom_l的题解 using namespace std; const int N=5e4+5; int n; vector<pair<int,int> >f[N]; int mn[N]; void work(vector<pair<int,int> >&p){ sort(p.begin(),p.end()); vector<pair<int,int> >tmp; for(auto i:p){ if(tmp.empty()||i.second+i.first*i.first<tmp.back().second+tmp.back().first*tmp.back().first)tmp.push_back(i); } p=tmp; } vector<int>e[N]; struct node{ int first,second,id; }; void dfs(int x,int fa){ for(int y:e[x]){ if(y==fa)continue; dfs(y,x); } int res=0; for(int y:e[x]){ if(y==fa)continue; mn[y]=1e18; for(auto i:f[y]){ int l=i.first,s=i.second; l++; mn[y]=min(s+l*l,mn[y]); } res+=mn[y]; } for(int y:e[x]){ if(y==fa)continue; for(auto i:f[y]){ int l=i.first,s=i.second; f[x].emplace_back(l+1,res-mn[y]+i.second); } } int ad=1e18; unordered_map<int,unordered_map<unsigned long long ,unordered_map<long long,int> > >mp; vector<node >tmp; for(int y:e[x]){ for(auto i:f[y]){ mp[i.first][i.second][mn[y]]++; if(mp[i.first][i.second][mn[y]]<=2)tmp.push_back({i.first,i.second,y}); } } for(auto i:tmp){ for(auto j:tmp){ if(i.id==j.id)continue; int tres=res-mn[i.id]-mn[j.id]; ad=min(ad,tres+i.second+j.second+(i.first+j.first+2)*(i.first+j.first+2)); } } f[x].emplace_back(0 , ad ); if(e[x].size()==1){ if(e[x][0]==fa){ f[x].emplace_back(0,0); } else { for(auto i:f[e[x][0]]){ f[x].emplace_back(0,i.second+(i.first+1)*(i.first+1)); } } } for(int y:e[x]){ if(y!=fa){ f[y].clear(); f[y].shrink_to_fit(); } } work(f[x]); } signed main (){ cin>>n; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; e[x].push_back(y); e[y].push_back(x); } dfs(1,0); if(f[1].empty()){ cout<<"E"; //调试时防止程序崩溃 exit(0); } cout<<f[1][0].second; return 0; }
by hansang:
#include<bits/stdc++.h> //by: hansang using namespace std; typedef long long LL; const int N=5e4+10; const LL inf=1e9; LL dep[N], dp[N]; int n, p[N]; //dp[i]为i子树的最小成本但缺少切割线有关的部分值（看calc函数和主函数注释），p数组表示偏移（启发式） struct node{ LL d, c, f; //层数，当前点切割线有关花费，特殊值（后面会解释） bool tag; //0表示切割线竖穿当前点（连接父节点和子节点），1表示切割线横穿当前点（连接两个子节点） }; vector<int> G[N]; set<node> b[N]; bool operator<(node a, node b) { if(a.tag || b.tag) return (a.f<b.f); //结合主函数的注释理解 if(a.d!=b.d) return (a.d>b.d); //非查找情况下 return (a.c<b.c); } LL sqe(LL x) {return x*x;} LL calc(node n1, node n2){ //这个函数是求出特殊值f（可以理解为斜率，那我们维护的就是一个下凸壳） if(n1.d>n2.d) swap(n1, n2); //这个函数面向dep较小的，联系79，100和127行自行理解 LL res=(sqe(n1.d)+n1.c-sqe(n2.d)-n2.c)/(2*(n2.d-n1.d)); //L^2+2*L*l+(l^2+c)，目前只有l和c确定，那么就先计算2*L*l+(l^2+c) //当前我们有2*L*l1+(l1^2+c1)和2*L*l2+(l2^2+c2) //相减得到：(l1^2+c1)-(l2^2+c2)+2*L*l1-2*L*l2 (一种符号) 0 //化一下： l1^2+c1-l2^2-c2 (一种符号) -2*(l1-L2)*L //将-2*(l1-L2)除过去(不用变号)，就有：(l1^2+c1-l2^2-c2)/(2*(l2-L1)(一种符号)L //当(一种符号)为大于号时，代表着2*L*l1+(l1^2+c1)>2*L*l2+(l2^2+c2) //而我们要改变L直到(一种符号)为小于或等于号，这样n1才比n2优 //就像这样：(l1^2+c1-l2^2-c2)/(2*(l2-L1)>L，只要不断给 L+1，总会变号的 while((sqe(n1.d)+n1.c-sqe(n2.d)-n2.c)>res*2*(n2.d-n1.d)) res++; //实际上，L(f)就代表着该节点较优时，子树外切割线的最小值，所以上面才按f排序 return res; } void dfs(int x, int fa) { LL res=-1, sum=0; //成本最小的切割线的目前x子树成本，不含切割线的目前x子树成本 for(auto y: G[x]) if(y!=fa){ dep[y]=dep[x]+1; dfs(y, x); auto n1=*(--b[p[y]].upper_bound({0, 0, -dep[x], 1})); //f查找x就代表着要查找子树外切割线为x的最优解 //如果n1的f!=dep[x]，那么t就会大一点 LL t=sqe(n1.d-dep[x])+n1.c+dp[y]; //由y的切割线延申到x if(res!=-1) res+=t; //如果y不是第一个子节点，就累计 if(b[p[x]].empty()){ //启发式，如果x没有切割线 swap(p[x], p[y]); dp[x]=dp[y]; //dp[y]=0; //到时候取答案会直接取x，dp[y]不重要 } else{ LL os=dp[x]+t, ot=dp[y]+sum; //分别为切割线在y上x的最小成本，切割线不在y上x的最小成本 if(b[p[x]].size()<b[p[y]].size()){ //启发式，如果y的切割线比x的多话 swap(p[x], p[y]); swap(os, ot); //不改dp的原因是os和ot后面会赋值dp } for(auto it: b[p[y]]){ //合并两条边 auto n2=*(--b[p[x]].upper_bound({0, 0, it.d-2*dep[x], 1})); //见39行 LL tmp=sqe(it.d+n2.d-2*dep[x])+it.c+n2.c+dp[x]+dp[y]; //把x的切割线和y的切割线连在一起 if(res==-1 || tmp<res) res=tmp; //找到了成本更小的切割线，更新 } for(auto it: b[p[y]]){ it.c+=ot-os; //加上差值，代表当前情况切割线变到x其它不变（感性理解 auto n2=b[p[x]].insert(it).first; //这里first代表着插入it之后it在set里的位置 bool flag=0; //当前解是否最深 while(n2!=b[p[x]].begin()){ //不是最深的（维护it前的下凸壳） auto n3=n2; n3--; if((*n3).d==it.d){ //有层数和当前一样的解还更优 b[p[x]].erase(n2); //删除当前解 flag=1; break; } node no=*n3; it.f=calc(no, it); //赋值 b[p[x]].erase(n2); n2=b[p[x]].insert(it).first; if(it.f<=(*n3).f) b[p[x]].erase(n3); //维护下凸壳 else break; } if(flag) continue; if(n2==b[p[x]].begin()){ //当前最深解 it.f=-inf; //第一个的特殊值为无穷小 b[p[x]].erase(n2); n2=b[p[x]].insert(it).first; } auto n3=n2; n3++; while(n3!=b[p[x]].end()){ //维护it后的下凸壳 if(it.d==(*n3).d){ //同上 b[p[x]].erase(n3); n3=n2; n3++; continue; } node no=*n3; no.f=calc(it, no); if(no.f<=it.f){ b[p[x]].erase(n2); break; } b[p[x]].erase(n3); n3=b[p[x]].insert(no).first; auto n4=n3; n4++; if(n4!=b[p[x]].end() && (*n4).f<=no.f) { b[p[x]].erase(n3); n3=n4; } else break; } } dp[x]=os; //更新（加上y的贡献） } sum+=t; } if(b[p[x]].empty()){ //没有切割线或叶子节点 b[p[x]].insert({dep[x], 0, -inf, 0}); //见88行 } else if(res!=-1){ //之前x有切割线（其实还是维护下凸壳） node tmp={dep[x], res-dp[x], 0, 0}; //res-dp[x]为x点最优切割线有关花费 while(!b[p[x]].empty()){ node n1=*b[p[x]].rbegin(); tmp.f=calc(n1, tmp); if(tmp.f>n1.f) break; else b[p[x]].erase(n1); //tmp更优 } if(b[p[x]].empty()) tmp.f=-inf; //同88行 b[p[x]].insert(tmp); //插入 } } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) p[i]=i; //偏移值初始化 for(int i=1; i<n; i++){ int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[ b ].push_back(a); } dep[1]=0; dfs(1, 0); auto it=b[p[1]].rbegin(); //取最后一个最靠近1的，含信息量高且因为维护过是最优的 printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); //1除切割线外花费+某点切割线花费+1到某点距离的平方 /* //其实原解是这样写的 if(G[1].size()==1){ auto it=--b[p[1]].upper_bound({0, 0, 0, 0}); printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); } else{ auto it=b[p[1]].rbegin(); printf("%lld\n", dp[1]+(*it).c+sqe((*it).d)); } //但我们发现第一种情况时，b[p[1]]里的f全都是负的 //upper_bound会返回end，所以两种情况可以合并 */ return 0; }
原题解：#include<bits/stdc++.h> using namespace std; typedef long long LL; struct poss { LL depth, cost, takeover; bool tcheck; }; bool operator<(poss a, poss b) { if (a.tcheck || b.tcheck) return (a.takeover < b.takeover); if(a.depth!=b.depth) return (a.depth > b.depth); return (a.cost < b.cost); } const int N=5e4+10; int n; vector<int> edges[N]; bool visited[N]; long long depth[N]; long long offset[N]; set<poss>* best[N];</p>void recurse(int node) { visited[node] = True; LL bestPair = -1; LL allSoFar = 0; for (int i = 0; i < edges[node].size(); i++) { if (visited[edges[node][i]]) continue; depth[edges[node][i]] = depth[node]+1; recurse(edges[node][i]);
LL tadd; { poss when = { 0, 0, -depth[node], True }; set<poss>::iterator which = best[edges[node][i]]->upper_bound(when); which--; tadd =(depth[node]-which->depth)*(depth[node]-which->depth)+which->cost+offset[edges[node][i]]; } if (bestPair != -1) bestPair += tadd;
if (best[node] == NULL) { best[node] = best[edges[node][i]]; offset[node] = offset[edges[node][i]]; } else { set<poss>* s = best[node], * t = best[edges[node][i]]; LL os = offset[node]+tadd, ot = offset[edges[node][i]]+allSoFar; if (s->size() < t->size()) { set<poss>* tem = s; s = t; t = tem; int to = os; os = ot; ot = to; } for (set<poss>::iterator it = t->begin(); it != t->end(); it++) { poss when = { 0, 0, it->depth-2*depth[node], True }; set<poss>::iterator which = s->upper_bound(when); which--; LL thisPair =(it->depth+which->depth-2depth[node])(it->depth+which->depth-2*depth[node])+it->cost+which->cost+offset[node]+offset[edges[node][i]]; if (bestPair == -1 || thisPair < bestPair) bestPair = thisPair; }
for (set<poss>::iterator it = t->begin(); it != t->end(); it++) { poss p = *it; p.cost += ot-os; set<poss>::iterator where = s->insert(p).first; bool killed = False; while (where != s->begin()) { set<poss>::iterator prev = where; prev--; if (prev->depth == where->depth) { s->erase(where); killed = True; break; } p.takeover =(where->cost-prev->cost+where->depthwhere->depth-prev->depthprev->depth)/(2prev->depth-2where->depth); while ((2prev->depth-2where->depth)p.takeover < where->cost-prev->cost+where->depthwhere->depth-prev->depth*prev->depth) p.takeover++; s->erase(where); where = s->insert(p).first;
if (where->takeover <= prev->takeover) s->erase(prev); else break; } if (killed) continue; if (where == s->begin()) { p.takeover = -1000000000; s->erase(where); where = s->insert(p).first; } set<poss>::iterator next = where; next++; while (next != s->end()) { if (next->depth == where->depth) { s->erase(next); next = where; next++; continue; } poss n = *next; n.takeover =(next->cost-where->cost+next->depthnext->depth-where->depthwhere->depth)/(2where->depth-2next->depth); while ((2where->depth-2next->depth)n.takeover < next->cost-where->cost+next->depthnext->depth-where->depth*where->depth) n.takeover++; if (n.takeover <= where->takeover) { s->erase(where); break; } s->erase(next); next = s->insert(n).first; set<poss>::iterator nnext = next; nnext++; if (nnext != s->end() && nnext->takeover <= next->takeover) { s->erase(next); next = nnext; } else break; } }
best[node] = s; offset[node] = os; delete t; } allSoFar += tadd; } if (best[node] == NULL) { best[node] = new set<poss>(); poss p = { depth[node], 0, -1000000000, False }; best[node]->insert(p); } else if (bestPair != -1) { poss p = { depth[node], bestPair-offset[node], 0, False }; while (!best[node]->empty()) { p.takeover =(p.cost-best[node]->rbegin()->cost+p.depthp.depth-best[node]->rbegin()->depthbest[node]->rbegin()->depth)/(2best[node]->rbegin()->depth-2p.depth); while ((2best[node]->rbegin()->depth-2p.depth)p.takeover < p.cost-best[node]->rbegin()->cost+p.depthp.depth-best[node]->rbegin()->depthbest[node]->rbegin()->depth) p.takeover++; if (p.takeover > best[node]->rbegin()->takeover) break; best[node]->erase((best[node]->rbegin())); } if (best[node]->empty()) p.takeover = -1000000000; best[node]->insert(p); } }
int main() { scanf("%d", &n); for (int i = 0; i < n-1; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; edges[a].push_back(b); edges[ b ].push_back(a); }
recurse(0); if (edges[0].size() == 1) { poss when = { 0, 0, 0, True }; set<poss>::iterator which = best[0]->upper_bound(when); which--; cout << which->depth*which->depth+which->cost+offset[0]<< endl; } else { poss p = *(best[0]->rbegin()); cout << p.cost+offset[0] << endl; } return 0; }
- 1
