(nlogn^2) 猜测的时间复杂度
要提高代码能力啊
要好好对拍
哇C题我还是太天真
理一下我的做题思路
首先我列举了一系列我应该处理的问题
1.判重
2.二分
3.选m条路
然后我猜可能跟
树形DP 倍增有关
然后我就想一条路满足的条件 可能是一条链或者转折一下
然后我想的太复杂 没有从细的地方想 就凉了.....
原来是我想的太复杂
我最后是写了一条链和直径的做法...
来看正解
容易想到的是用树形DP，同时题面要求的是“最短长度最长”，就是明显的二分答案
那么我们首先应从二分答案开始入手
尽可能多地选满足条件的边
那么应该从一颗小树开始研究
他选边的条件 就是选转折边或者是选一条链
那怎样统计答案呢
这时候我们就想到了树形DP
令(f[i])表示i为根的子树最多能选的条数
(g[i])表示 i为根的子树最大能贡献的边的长度
贪心一下每次选最小的边配最近满足条件的边
已经大于二分val的可以直接记录到答案中
muiltiset即可 注意判重
因为选的是
这题也可以二分 把这条边删去看还能否满足条件
因为选子树的一定是最优的
code：
注意STL lower_bound的时候一定要判断是否为空
muitiset
#include<stdio.h>
#include<set>
#include<iostream>
#include<cstdio>
using namespace std;
#define maxnn 100010
#define _maxnn 200100
int f[maxnn];
int g[maxnn],res[maxnn];
int las[_maxnn],en[_maxnn],nex[_maxnn],tot,le[_maxnn];
int n,m;
void add(int a,int b,int c) {
en[++tot]=b;
nex[tot]=las[a];
las[a]=tot;
le[tot]=c;
}
void dfs(int v,int fa) {
f[v]=fa;
for(int i=las[v]; i; i=nex[i]) {
int u=en[i];
if(u!=fa) {
dfs(u,v);
}
}
}
void prdfs(int v,int fa,int lo) {
multiset<int > Q;
multiset<int > ::iterator it;
multiset<int > :: iterator pos;
int tmp=0;
for(int i=las[v]; i; i=nex[i]) {
tmp=0;
int u=en[i];
if(u!=fa) {
prdfs(u,v,lo);
tmp=g[u]+le[i];
if(tmp>=lo) res[v]++;
else
Q.insert(tmp);
}
}
int maxx=0;
while(Q.size())
{
multiset<int > ::iterator pos;
pos=Q.lower_bound(lo-*Q.begin());
if(Q.size()==1)
{
maxx=max(maxx,*Q.begin());
break;
}
if(pos==Q.begin())
{
pos++;
}
if(pos==Q.end())
{
maxx=max(maxx,*Q.begin());
Q.erase(Q.begin());
}
else
{
res[v]++;
Q.erase(Q.begin());
Q.erase(pos);
}
}
g[v]=maxx;
}
int isok(int t) {
for(int i=1; i<=n; i++) {
res[i]=0;
g[i]=0;
}
prdfs(1,1,t);
int cnt=0;
for(int i=1; i<=n; i++) {
cnt+=res[i];
}
return cnt;
}
int main() {
// freopen("track3.in","r",stdin);
// freopen("o","w",stdout);
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1; i<n; i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,1);
int l=0,r=600000000;
while(l<=r) {
int mid=(l+r)/2;
if(isok(mid)>=m) {
l=mid+1;
} else {
r=mid-1;
}
}
printf("%d",r);
}
vector:
while(!s[x].empty()){
if(s[x].size()==1){
return max(Max,*s[x].begin());
}
it=lower_bound(s[x].begin(),s[x].end(),k-*s[x].begin());
if(it==s[x].begin()) it++;
if(it==s[x].end()){
Max=max(Max,*s[x].begin());
s[x].erase(s[x].begin());
}
else {
ans++;
s[x].erase(it);
s[x].erase(s[x].begin());
}
}
return Max;