这题思路大佬们都讲了,我来讲哈我的做法
不知道为啥,大佬们都用的双指针...虽然感觉上对的,而且我hack不掉,但是我总感觉有某种神奇的数据会让他出问题.于是,我选择用set
双指针比较头尾貌似挺有道理,但是我总感觉如果他的子树能配对,传上去的数一定是最大的.而双指针不能保证传上去的是最大的数.比如1 3 5 6 10.假设要选的数是7,双指针会选1 10, 3 6, 然后返回一个5.然而我们可以划分为1 6和3 5,返回10(如果有理解错,欢迎指正)
而set的方法就好写多了.每次配对子树的时候,我们只选最小能使子树配对满足要求的数.这个操作可以用lower_bound做.如果用vector可以用二分实现(但码量就大不少了).
更新答案有几种情况(必须在出发点才更新答案):
1.如果出发点的子树全部能配对,那么这个数是可以选的
2.如果出发点含有的未配对子树,并且子树的权值 (>=) 我们要选的数,那么这个数是可以选的
这些都有一个共同的前提:他的子树能够成功配对.
如果有任何一个子树不能配对,那么这个数绝对不能选
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 1e5+5;
int n,st;
vector<int> adj[MAXN];
bool possible = true;
inline int dfs(int pos, int fa,int num){
multiset<int> se;
int tmp = 0,sz = 0;
for (int v : adj[pos]){
if(!possible) return -1;
if (v==fa) continue;
int k = dfs(v,pos,num);
if (!possible) return -1;
se.insert(k);
}//基本操作
while(se.size()>1 && possible){
auto it = se.begin(); se.erase(se.begin());
if ((*it)>=num) continue;
auto it2 = se.lower_bound(num-(*it));
if (it2!=se.end()){//如果能配对
if (se.size()==1 && *it2>=num && !sz) return (*it2)+1;//如果子树的数量只有一个,并且没有未配对的子树,就将这个数返回
se.erase(it2);
}else sz++,tmp+=(*it);//如果这棵子树不能配对
if (sz>1) possible = false;//如果有两棵不能配对的子树,那么这棵树不成立
}
if (!possible) return -1;
if (pos==1 && (sz || (se.size() && *se.begin()<num))) return 0;//不成立的条件有:在起点并且有未配对的子树或者剩下的子树的权值小于要求的数
if (pos==1) return sz>1 ? 0 : (!se.size() || !sz || (*se.begin()>=num)) ? 1e5 : 0;//上面讲过的
if (!se.size()) return tmp+1;//如果这个数没有子树了,就将配对剩下来的数返回
if (*se.begin()<num && sz) {possible = false;return -1;}//如果这个数的剩余子树的权值<这个数,并且还有其他未配对的子树
else if (*se.begin()>=num && sz) return tmp+1;//如果他有未配对的子树,但剩余子树的权值>=要求的数
else if (!sz) return *se.begin()+1;//如果没有未配对子树
}
int a,b;
inline void bs(){
int l = 1, r = n-1;
while(l!=r){
int mid = (l+r+1)/2;
possible = true;
int re = dfs(1,-1,mid);
if (possible && re>=mid) l = mid;
else r = mid-1;
}
cout << r;
}
int main(){
cin >> n;
for (int i=0;i<n-1;i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
bs();
}