program vjiosP1553;

type
        point=^node;
        node=record
                data,w:longint;
                next:point;
        end;
var
        n,s:longint;
        head:array[1..500050] of point;
        list:array[1..500050] of longint;
        lists:longint;
        visit,flag:array[1..5000050] of boolean;
        pre,pred,sum,f:array[1..500050] of longint;
        key,max:longint;
        ans:longint;
        queue,qt:array[1..500050] of longint;
        qhead,qtail:longint;

function maxf(a,b:longint):longint;
begin
        if a>b then
                exit(a)
        else
                exit(b);
end;

function minf(a,b:longint):longint;
begin
        if a<b then
                exit(a)
        else
                exit(b);
end;

procedure initdfs;
begin
        fillchar(visit,sizeof(visit),0);
        fillchar(pre,sizeof(pre),0);
        fillchar(pred,sizeof(pred),0);
        max:=0;
end;

procedure initq;
begin
        qhead:=1;
        qtail:=1;
end;

procedure put(data,id:longint);
var
        tmp:longint;
begin
        tmp:=qhead;
        while queue[tmp]>data do
                inc(tmp);
        queue[tmp]:=data;
        qt[tmp]:=id;
        qtail:=tmp;
end;

function find(l:longint):longint;
begin
        while qt[qhead]<l do inc(qhead);
        exit(queue[qhead]);
end;

procedure initp(x:longint);
begin
        head[x]:=nil;
end;

procedure insert(u,v,w:longint);
var
        p:point;
begin
        new(p);
        p^.data:=v;
        p^.w:=w;
        p^.next:=head[u];
        head[u]:=p;
end;

procedure inputdata;
var
        i:longint;
        u,v,w:longint;
begin
        fillchar(flag,sizeof(flag),false);
        readln(n,s);
        for i:=1 to n do
                initp(i);
        for i:=1 to n-1 do
        begin
                readln(u,v,w);
                insert(u,v,w);
                insert(v,u,w);
        end;
end;

procedure dfs(id,dist:longint);
var
        now:point;
        nowid,nowd:longint;
begin
        visit[id]:=true;
        now:=head[id];
        while now<>nil do
        begin
                nowid:=now^.data;
                nowd:=dist+now^.w;
                if (not visit[nowid]) and (not flag[nowid]) then
                begin
                        pre[nowid]:=id;
                        pred[nowid]:=now^.w;
                        if nowd>max then
                        begin
                                key:=nowid;
                                max:=nowd;
                        end;
                        dfs(nowid,nowd);
                end;
                now:=now^.next;
        end;
end;

procedure work1;
var
        now,t:longint;
        i:longint;
begin
        initdfs;
        pre[1]:=1;
        dfs(1,0);
        initdfs;
        pre[key]:=key;
        pred[key]:=0;
        dfs(key,0);

        fillchar(sum,sizeof(sum),0);
        lists:=1;
        list[1]:=key;
        t:=pred[key];
        now:=pre[key];
        while pre[now]<>now do
        begin
                inc(lists);
                list[lists]:=now;
                sum[lists]:=sum[lists-1]+t;
                t:=pred[now];
                now:=pre[now];
        end;
        inc(lists);
        list[lists]:=now;
        sum[lists]:=sum[lists-1]+t;
        for i:=1 to lists do
                flag[list[i]]:=true;
end;

procedure work2;
var
        i:longint;
begin
        for i:=1 to lists do
        begin
                initdfs;
                dfs(list[i],0);
                f[i]:=max;
        end;
end;

procedure work3;
var
        tl,tr:longint;
        tot,tmp:longint;
begin
        ans:=200000000; initq;
        tl:=1;  tr:=1;  put(f[1],1);
        repeat
                while (sum[tr+1]-sum[tl]<=s) and (tr<lists) do
                begin
                        inc(tr);
                        put(f[tr],tr);
                end;
                tot:=0;
                tot:=maxf(sum[tl],find(tl));
                tot:=maxf(tot,sum[lists]-sum[tr]);
                ans:=minf(ans,tot);

                inc(tl);
                 if tr>=lists then break;
        until tr=lists;
end;

begin
        inputdata;
        work1;
        work2;
        work3;
        writeln(ans);
end.

Accepted 有效得分：100 有效耗时：3200ms

数据果然弱:

1.DP的时候原本直接递归,但是这样就栈溢出,于是限制递归层数不超过10000,这样有一些点可能就错了,但是没错...

2.懒得写RMQ了,直接枚举的...

1可能为2节约了时间,才卡时通过的.

BFS+DFS+单调队列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 244ms

├ 测试数据 08：答案正确... 212ms

├ 测试数据 09：答案正确... 666ms

├ 测试数据 10：答案正确... 556ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1784ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 103ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 338ms

├ 测试数据 08：答案正确... 338ms

├ 测试数据 09：答案正确... 806ms

├ 测试数据 10：答案正确... 791ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2638ms

O（N）算法，常数巨大。

多亏了PUPPY。

我是神牛！大家来膜拜我！！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 462ms

├ 测试数据 10：答案正确... 416ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1118ms

就400000还这样,输入输出常数很大

我也是O(n)的,可怎么会这样......

难道是因为用了class?

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 56ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 244ms

├ 测试数据 05：答案正确... 244ms

├ 测试数据 06：答案正确... 228ms

├ 测试数据 07：答案正确... 431ms

├ 测试数据 08：答案正确... 447ms

├ 测试数据 09：答案正确... 884ms

├ 测试数据 10：答案正确... 931ms

O(n)吧

写O(n)算法就能AC……

还有这题可能卡C++的读入……

还有s

哈哈哈哈哈哈哈啊哈哈哈哈啊哈哈

汗，第一次交成朴素的了……

bfs + 单调队列