record

简要思路（应该很少人想这么复杂的思路）：先取最靠近直径中点的点为根，再进行鬼畜的不知道是双指针还是树形dp的东西就得到了答案序列，然后再bfs一遍求偏心距。

然后对于第一个样例的答案是9，但是过了？！

代码问题：在取最靠近直径中点的点为根这一步上把 max 函数写成 min 了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000;

struct node
{
	int note,value;
}dn[MAXN + 10];

bool vis[MAXN + 10];
int n,s,dp[MAXN + 10],d,dm,df;
vector <node> con[MAXN + 10];

void dfs(int x,int fa)
{
	dp[x] = dn[x].note = dn[x].value = 0;
	for(int i = 0;i < con[x].size();i++)
	{
		const node to = con[x][i];
		if(to.note == fa)
		    continue;
        dfs(to.note,x);
        const int now = dp[to.note] + to.value;
        if(now + dp[x] > d)
        {
        	d = now + dp[x];
        	dm = x;
        	df = fa;
		}
		if(now > dp[x])
		{
			dp[x] = now;
			dn[x] = to;
		}
	}
}

pair <node,node> un9(int x,int fa)
{
	node m1{0,0},m2{0,0}; 
	for(int i = 0;i < con[x].size();i++)
	{
    	const node to = con[x][i];
    	const int now = dp[to.note] + to.value;
    	if(now > m2.value + dp[m2.note])
    	    m2 = to;
	    if(m2.value + dp[m2.note] > m1.value + dp[m1.note])
	        swap(m2,m1);
	}
	return make_pair(m1,m2);
}

int main()
{
	scanf("%d %d",&n,&s);
	for(int i = 0;i < n - 1;i++)
	{
		int f,t,v;
		scanf("%d %d %d",&f,&t,&v);
		con[f].push_back(node{t,v});
		con[t].push_back(node{f,v});
	}
	dfs(1,0);
	
	deque <node> la;
	node d2{0,0};
	for(int i = 0;i < con[dm].size();i++)
    {
    	const node to = con[dm][i];
    	if(to.note == df || to.note == dn[dm].note)
    	    continue;
	    const int now = dp[to.note] + to.value;
	    if(now > dp[d2.note] + d2.value)
	        d2 = to;
	}
	for(int ls = dm;ls;ls = dn[ls].note)
	    la.push_front(node{ls,dn[ls].value});
    for(;d2.note;d2 = dn[d2.note])
        la.push_back(d2);
    
    int spot = la.front().note,v = 0;
    la.pop_front();
    while(v + la.front().value <= (d + 1) / 2)
    {
    	v += la.front().value;
    	spot = la.front().note;
    	la.pop_front();
	}
	const int nxt = v + la.front().value;
	if(min(d - nxt,nxt) < min(d - v,v))
	    spot = la.front().note;
    d = 0;
    dfs(spot,0);
    
    pair <node,node> re = un9(spot,0);
    int ans = 0;
    node l,r;
    l = re.first;
    r = re.second;
    v = 0;
    vector <int> c;
    c.push_back(spot);
    while(v + l.value <= s)
    {
		v += l.value;
        c.push_back(l.note);
        l = dn[l.note];
        if(dp[l.note] + l.value < dp[r.note] + r.value)
            swap(l,r);
        if(l.note == 0)
            break;
	}
	
	queue <node> q;
	for(int i = 0;i < c.size();i++)
    {
	    q.push(node{c[i],0});
	    vis[c[i]] = true;
	}
    while(q.size())
    {
    	const node ls = q.front();
    	q.pop();
    	ans = max(ans,ls.value);
    	for(int i = 0;i < con[ls.note].size();i++)
    	{
    		const node to = con[ls.note][i];
    		if(vis[to.note])
    		    continue;
		    q.push(node{to.note,ls.value + to.value});
		    vis[to.note] = true;
		}
	}
	printf("%d",ans);
	return 0;
}