Dylan's Blog
0%

Posted on Edited on In

A - F & B - Acrostic

过水 QWQ…

C - Ordinary Beauty

思路： 一道比较巧妙的数学题。我们其实只需要考虑一位的期望，然后整个序列的期望就是这个的m+1倍。

然后我们考虑如何计算期望。一共是有$n*n$种情况（只考虑一位），如果$d==0$时，显然是有$n$种情况符合要求，如果$d!=0$那么就有$(n-d)*2$种情况符合要求，所以分类讨论一下就好。还有一点就是要注意精度，不要一下除$n*n$，精度损失比较大。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstring>
#define LL long long
using namespace std;

LL n, m, d;

int main()
{
    scanf("%lld%lld%lld", &n, &m, &d);
    double temp;
    if(d==0) temp=n;
    else temp=(n-d)*2;
    printf("%.10lf\n", (double)(m-1)/n*temp/n);
}

D - Saving Snuuk

思路： 比较水的一道图论题，只是题目好难看懂啊。。。其实就是给你一张无向图，每条边有两种权值，然后求在每个点切换权值的最短路。

不难想到建两张图，分别从起点，终点跑SPFA。每个点切换权值的最短路就是到起点，终点的距离之和。 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 100005

LL min(LL x, LL y) {if(x<y) return x; return y;}

int n, m, s, t, u, v;
LL a, b, f=1e15, ans[MAXN];

struct Graph
{
    int cnt, head[MAXN], vis[MAXN];
    LL dis[MAXN];

    struct Edge {int next, to; LL dis;} edge[MAXN*2];

    std::queue<int> q;

    void addedge(int from, int to, LL dis)
    {
        edge[++cnt].next=head[from];
        edge[cnt].to=to;
        edge[cnt].dis=dis;
        head[from]=cnt;
    }

    void spfa(int s)
    {
        for(int i=1; i<=n; i++) dis[i]=INF;
        memset(vis, 0, sizeof(vis));
        q.push(s); vis[s]=1; dis[s]=0;
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            vis[x]=0;
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]>dis[x]+edge[i].dis)
                {
                    dis[to]=dis[x]+edge[i].dis;
                    if(!vis[to]) q.push(to), vis[to]=1;
                }
            }
        }
    }
} g1, g2;

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%lld%lld", &u, &v, &a, &b);
        g1.addedge(u, v, a); g1.addedge(v, u, a);
        g2.addedge(v, u, b); g2.addedge(u, v, b);
    }
    g1.spfa(s);  g2.spfa(t);
    ans[n+1]=INF;
    for(int i=n; i>=1; i--) ans[i]=min(ans[i+1], g1.dis[i]+g2.dis[i]);
    for(int i=1; i<=n; i++) printf("%lld\n", f-ans[i]);
}

E - + Graph

思路： 思维难度不大，只是超级考验码力，我比赛时调了超级久还是没有写出QWQ。

我们设节点1的值为x，然后其它所有点的值都可以用$w_1-x$或$w_2+x$表示（w可以根据题目条件推出来）。先bfs一遍处理出每个节点$w_1,w_2$，储存在f数组里，然后统一进行判断。

限制条件有很多，不要漏了。首先要判断是否有正整数解，还要判断解的范围，还要判断解是否在范围内。详细的看代码好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF 1e18
#define LL long long

int n, m, cnt, head[MAXN], vis[MAXN];
LL l=1, r=INF, root=-1, f[MAXN][5];

LL min(LL x, LL y) {if(x>y) return y; return x;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

struct Edge{int next, to; LL dis;} edge[MAXN];

std::queue<int> q;

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int x)
{
    vis[x]=1; q.push(x);
    f[x][0]=1; f[x][1]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            f[to][0]=-f[x][0];
            f[to][1]=edge[i].dis-f[x][1];
            vis[to]=1; q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int u, v, s;
        scanf("%d%d%d", &u, &v, &s);
        addedge(u, v, s);
        addedge(v, u, s);
    }
    bfs(1);
    for(int i=1; i<=n; i++)
    {
        if(f[i][0]==1) l=max(l, 1-f[i][1]);
        else r=min(r, f[i][1]-1);
        for(int j=head[i]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            LL x=f[i][0]+f[to][0];
            LL y=f[i][1]+f[to][1];
            if(x==0 && y!=edge[j].dis) {printf("0\n"); return 0;}
            if(x!=0)
            {
                LL temp=edge[j].dis-y;
                if(temp%2 || temp/x<=0) {printf("0\n"); return 0;}
                if(root==-1) root=temp/x;
                if(root!=temp/x) {printf("0\n"); return 0;}
            }
        }
    }
    if(root==-1) printf("%lld\n", max(0, r-l+1));
    else printf("%d", (root>=l && root<=r));
}

Posted on Edited on In

问题描述：

给你一张有n个节点m条边的无向图，需要你求出这张图的严格次小生成树。

输入：

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出：

仅一个数，表示严格次小生成树的边权和。

思路：

这道题和POJ1639度限制生成树一样，先计算出最小生成树，然后在最小生成树的基础上进行调整，得到要求的答案。

我们知道最小生成树与次小生成树最多只有一条边不同。所以我们可以在已经求出最小生成树的基础上，枚举每一条不在树上的边。假设它是次小生成树上的边，那么我们既要保持树的结构还要使树尽可能小，这时我们就要删去这条边两端树上路径的最长边，然后利用这个更新答案。

但这就出现了一个问题，有可能这条删去的边的边权和我们加的边的边权相等，这时新的树依然是最小生成树。所以我们需要记录下两端树上路径的次长边，如果出现上面情况我们就删去次长边，这样就是严格树次小生成树了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define MAXE 300005
#define LL long long
#define INF 1e18
using namespace std;

int n, m, cnt, max1, max2, head[MAXN], f1[MAXN], f2[MAXN][25], dis[MAXN][25][2], dep[MAXN];
LL sum, ans=INF;

struct Edge {int x, y, dis; bool tag;} edge[MAXE];
struct Tree {int next, to, dis;} tree[MAXN*2];

bool CMP (Edge x, Edge y) {return x.dis<y.dis;}

int find(int x)
{
    if(f1[x]!=x) f1[x]=find(f1[x]);
    return f1[x];
}

void addedge(int from, int to, int dis)
{
    tree[++cnt].next=head[from];
    tree[cnt].to=to;
    tree[cnt].dis=dis;
    head[from]=cnt;
}

void kruskal()
{
    for(int i=1; i<=n; i++) f1[i]=i;
    sort(edge+1, edge+m+1, CMP);
    for(int i=1; i<=m; i++)
    {
        int fx=find(edge[i].x), fy=find(edge[i].y);
        if(fx!=fy)
        {
            f1[fx]=fy; sum+=edge[i].dis;
            edge[i].tag=true;
            addedge(edge[i].x, edge[i].y, edge[i].dis);
            addedge(edge[i].y, edge[i].x, edge[i].dis);
        }
    }
}

void dfs(int x, int fa)
{
    f2[x][0]=fa;
    for(int i=head[x]; i; i=tree[i].next)
    {
        int to=tree[i].to;
        if(to==fa) continue;
        dis[to][0][0]=tree[i].dis;
        dep[to]=dep[x]+1;
        dfs(to, x);
    }
}

void init()
{
    for(int i=1; i<=20; i++)
    {
        for(int j=1; j<=n; j++)
        {
            f2[j][i]=f2[f2[j][i-1]][i-1];
            dis[j][i][0]=max(dis[j][i-1][0], dis[f2[j][i-1]][i-1][0]);
            dis[j][i][1]=max(dis[j][i-1][1], dis[f2[j][i-1]][i-1][1]);
            if(dis[f2[j][i-1]][i-1][0]==dis[j][i-1][0]) continue;
            dis[j][i][1]=max(dis[j][i][1], min(dis[f2[j][i-1]][i-1][0], dis[j][i-1][0]));
        }
    }
}

int Lca(int x, int y)
{
    if(dep[x]<dep[y]) swap(x, y);
    for(int i=20; i>=0; i--) if(dep[f2[x][i]]>=dep[y]) x=f2[x][i];
    if(x==y) return x;
    for(int i=20; i>=0; i--) if(f2[x][i]!=f2[y][i]) x=f2[x][i], y=f2[y][i];
    return f2[x][0];
}

int solve(int x, int y, int len)
{
    int maxn=0;
    for(int i=20; i>=0; i--)
    {
        if(dep[f2[x][i]]>=dep[y])
        {
            if(dis[x][i][0]==len) maxn=max(maxn, dis[x][i][1]);
            else maxn=max(maxn, dis[x][i][0]);
            x=f2[x][i];
        }
    }
    return maxn;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].dis);
    kruskal();
    dfs(1, 0);
    init();
    for(int i=1; i<=m; i++)
    {
        if(edge[i].tag) continue;
        int lca=Lca(edge[i].x, edge[i].y);
        max1=solve(edge[i].x, lca, edge[i].dis);
        max2=solve(edge[i].y, lca, edge[i].dis);
        ans=min(ans, sum-max(max1, max2)+edge[i].dis);
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

7月1日 AtCoder Regular Contest 100 题目链接: https://arc100.contest.atcoder.jp/

C - Linear Approximation

思路： 首先看到那个式子比较复杂，其实可以将它化简，把第i项减去i。然后观察式子可以发现那个值就是序列的中位数，然后直接算出答案。其实这就是那个货仓选址的模型，比较重要。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n;
LL ans, a[200005];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]-=i;
    sort(a+1, a+n+1);
    LL t=a[(n+1)/2];
    for(int i=1; i<=n; i++)
    {
        if(a[i]-t<0) ans+=t-a[i];
        else ans+=a[i]-t;
    }
    printf("%lld\n", ans);
}

D - Equal Cut

思路： 玄学。。。首先可以枚举中间切的那一刀，由于我们希望极差最小，所以有一种感觉就是要分得尽量平均。因此对于中间的每一刀，我们可以确定出左边和右边两刀，把序列左边和右边切得更“平均”，用这个更新答案。其实有一点迷QWQ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 200005
using namespace std;

int n;
LL a[MAXN], ans=INF;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]+=a[i-1];
    int l=1, r=3;
    LL maxn, minn;
    for(int i=2; i<=n-2; i++)
    {
        while(a[l]<a[i]-a[l]) l++;
        while(a[r]-a[i]<a[n]-a[r]) r++;
        if(a[l-1]>a[i]-a[l]) l--;
        if(a[r-1]-a[i]>a[n]-a[r]) r--;
        maxn=max(max(a[l], a[i]-a[l]), max(a[r]-a[i], a[n]-a[r]));
        minn=min(min(a[l], a[i]-a[l]), min(a[r]-a[i], a[n]-a[r]));
        ans=min(ans, maxn-minn);
    }
    printf("%lld\n", ans);
}

E - Or Plus Max

思路： 发现自己位运算是真的菜。。。。

类似于一个DP。首先枚举下标0到1<<n，如果下标x的第i位上是0（二进制）那么它一定包含于（同样是二进制）下标 x&(1<<i)（也就是把那一位变为1）。所以可以用下标x的数来更新下标x&(1<<i)的数之前的最大值。 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define MAXN 300005
#define LL long long
using namespace std;

int n, f[MAXN][2];
LL ans[MAXN], a[MAXN];

void solve(int x, int y)
{
    if(f[x][0]==y || f[x][1]==y) return;
    if(a[f[x][1]]<a[y])
    {
        f[x][1]=y;
        if(a[f[x][0]]<a[f[x][1]]) swap(f[x][0], f[x][1]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=0; i<(1<<n); i++)
    {
        scanf("%lld", &a[i]);
        f[i][0]=i;
    }
    for(int i=0; i<(1<<n); i++) for(int j=0; j<n; j++)
    {
        if((i>>j)&1) continue;
        solve(i|(1<<j), f[i][0]);
        solve(i|(1<<j), f[i][1]);
    }
    for(int i=1; i<(1<<n); i++)
    {
        ans[i]=max(ans[i-1], a[f[i][0]]+a[f[i][1]]);
        printf("%lld\n", ans[i]);
    }
}

Posted on Edited on In

6月24日 Lydsy1806月赛 题目链接：https://www.lydsy.com/JudgeOnline/contest.php?cid=1014

A - 字符串大师II

思路： 其实没有什么思路的。border数组就是是KMP中的next，然后就打表找一下规律，就发现了结论:$ans=p-2^{log2(k)}$。

但是要注意一点，当k很大时$log2(k)$会被卡精度。开一个数组sec记录$log2(k)$为多少就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;

LL t, k, p, sec[100], temp;

int main()
{
    scanf("%lld", &t);
    sec[0]=1;
    for(int i=1; i<=60; i++) sec[i]=sec[i-1]*2;
    for(int i=1; i<=t; i++)
    {
        scanf("%lld%lld", &k, &p);
        for(int j=1; j<=60; j++)
        {
            if(p>=sec[j-1] && p<sec[j])
            {
                temp=j-1;
                break;
            }
        }
        printf("%lld\n", p-((LL)1<<temp));
    }
}

B - 超速摄像头

思路： 由于道路是树的结构，所以越外层节点数越多，因此我们尽量选外层的节点装摄像头。

然后直接模拟，所有入度为1的节点为最外层，然后删掉最外层节点并k-2。重复此操作直到k<=2，如果最后k=1时，则再可以给任意一个节点装摄像头。最后统计一下答案就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#define LL long long
#define rint register int
#define MAXN 1000005
using namespace std;

int n, k, ans, cnt, top1, top2, head[MAXN], deg[MAXN], sta[MAXN], temp[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    deg[to]++;
    head[from]=cnt;
}

int main()
{
    int x, y;
    scanf("%d%d", &n, &k);
    if(k==1) {printf("1\n"); return 0;}
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for(int i=1; i<=n; i++) if(deg[i]==1) sta[++top1]=i, vis[i]=1;
    k-=2;
    while(k>=2 && top1>0)
    {
        for(int j=1; j<=top1; j++)
        {
            int x=sta[j];
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(vis[to]) continue;
                deg[to]--;
                if(deg[to]==1) temp[++top2]=to;
            }
        }
        top1=top2;
        for(int i=1; i<=top2; i++) sta[i]=temp[i], vis[temp[i]]=1;
        k-=2; top2=0;
    }
    for(int i=1; i<=n; i++)
    {
        if(vis[i]) ans++;
        else if(k>0) k--, ans++;
    }
    printf("%d\n", ans);
}

C - 质数拆分

思路： 比较暴力的枚举吧。设f[i]为两个质数和为i的方案数，通过枚举计算出f数组。答案就是i从1到n $f[i]*f[n-i]$的和

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int n, tot, prime[150005], f[150005], check[150005];
long long ans;

int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        if(!check[i]) prime[++tot]=i;
        for(int j=1; j<=tot && i*prime[j]<=n; j++)
        {
            check[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1; i<=tot && prime[i]*2<=n; i++)
    {
        f[prime[i]*2]++;
        for(int j=i+1; j<=tot && prime[i]+prime[j]<=n; j++) f[prime[i]+prime[j]]+=2;
    }
    for(int i=1; i<=n/2; ++i) ans+=f[i]*f[n-i]*2;
    if(n%2==0) ans-=f[n/2]*f[n/2];
    printf("%lld\n", ans);
}

E - 比例查询

思路： 特别好的一道题。对于这种序列问题，不能够区间合并，离线可能是一种做法。这道题的离线思想和BZOJ1878 HH的项链有点像。

设f[i]为数i最近的位置，g[i]为比例为i的两个数最近的位置。先将询问的右端点排序，然后从左向右扫。每扫到一个数找它的约数，用这个来跟新f[i],g[i]，如果有询问的右端点在扫到的位置上，就根据g[i]回答询问。

但要注意，我们从左到右扫是是默认了右边的数为左边的数的b倍，因此我们需要再从右向左扫一遍。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n, m, a[MAXN], f[MAXN], g[MAXN], ans[MAXN];

struct Q {int l, r, b, pos;} q[MAXN];

bool CMP(Q x, Q y) {return x.r<y.r;}

void solve()
{
    sort(q+1, q+m+1, CMP);
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for(int i=1, j=1; i<=n; i++)
    {
        for(int k=1; k*k<=a[i]; k++)
        {
            if(a[i]%k) continue;
            g[k]=max(g[k], f[a[i]/k]);
            g[a[i]/k]=max(g[a[i]/k], f[k]);
        }
        f[a[i]]=i;
        for(; q[j].r==i; j++) if(g[q[j].b]>=q[j].l) ans[q[j].pos]=1;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)  scanf("%d", &a[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].b);
        q[i].pos=i;
    }
    solve();
    reverse(a+1, a+n+1);
    for(int i=1; i<=m; i++)
    {
        q[i].l=n-q[i].l+1;
        q[i].r=n-q[i].r+1;
        swap(q[i].l, q[i].r);
    }
    solve();
    for(int i=1; i<=m; i++)
    {
        if(ans[i]) printf("Yes\n");
        else printf("No\n");
    }
}

G - 最长公共子序列

思路： 一道结论题，当T全为一个字母时是最优的，因此答案就是出现次数最少的字母的出现数。（凭感觉吧，不太会证明）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int num[30], ans=1e9, len;
char s[1000005];

int main()
{
    scanf("%s", s);
    len=strlen(s);
    for(int i=0; i<len; i++) num[s[i]-'a']++;
    for(int i=0; i<26; i++) ans=min(ans, num[i]);
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述:

简单来说，就是给你一棵树，在直径上找一个长度不超过s的链，使得偏心距最小。偏心距的定义为：树上到这条链最远的节点到这条链的距离。

输入:

包含n行： 第1行，两个正整数n和s。其中n为树网结点的个数，s为树网的核的长度的上界。 从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。

注：NOIP原题数据:n<=300，BZOJ加强数据:n<=500000

输出:

只有一个非负整数，为指定意义下的最小偏心距。

思路:

首先想NOIP数据范围的做法，因为我们找的链是在直径上。所以我们可以先处理出直径再暴力枚举直径上的链。因为链长要小于等于ｓ，我们可以枚举一个端点，然后尽可能远的在链上找到另一个端点。这样我们就$O(n)$暴力枚举处理所有链，对于每一条链用一次dfs找出偏心距就OK了。

然后再考虑BZOJ加强版数据，枚举一个端点，然后尽可能远的在链上找到另一个端点。但是我们可以不需要对于每一条链都找出偏心距，我们可以利用直径的性质$O(n)$统一处理出答案。

代码:

$O(n^2)$暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 3005
#define INF 0x3f3f3f3f
using namespace std;

int n, s, root, cnt, ans=INF, ecc, head[MAXN], dis[MAXN], pre[MAXN];
bool vis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int root)
{
    queue<int> q;
    vis[root]=true; q.push(root);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            pre[to]=x; vis[to]=true;
            dis[to]=dis[x]+edge[i].dis;
            q.push(to);
        }
    }
}

void getline()
{
    int maxdis=0;
    bfs(1);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    memset(dis, 0, sizeof(dis));
    bfs(root);
    maxdis=0;
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], root=i;
}

void dfs(int x, int fa, int dis)
{
    ecc=max(ecc, dis);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dfs(to, x, edge[i].dis+dis);
    }
}

void solve()
{
    for(int x=root; x; x=pre[x])
    {
        int y=0, len=0; ecc=0;
        memset(vis, 0, sizeof(vis));
        for(int i=x; i; i=pre[i])
        {
            for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to==pre[i]) len+=edge[j].dis;
            y=i; vis[i]=true;
            if(len>s) break;
        }
        for(int i=x; ; i=pre[i])
        {
            dfs(i, 0, 0);
            if(i==y) break;
        }
        ans=min(ans, ecc);
    }
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve();
    printf("%d\n", ans);
}

$O(n)$做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define LL long long
#define MAXN 500005

LL min(LL x, LL y) {if(x<y) return x; return y;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

int n, s, lpnt, rpnt, cnt, head[MAXN], pre[MAXN];
LL  ans=1e18, dis[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void dfs(int x, int fa)
{
    pre[x]=fa;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        dis[to]=dis[x]+edge[i].dis;
        dfs(to, x);
    }
}

void getline()
{
    LL maxdis=0; dis[1]=0;
    dfs(1, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], lpnt=i;
    maxdis=0; dis[lpnt]=0;
    dfs(lpnt, 0);
    for(int i=1; i<=n; i++) if(dis[i]>maxdis) maxdis=dis[i], rpnt=i;
}

void solve()
{
    int l=rpnt, r=rpnt;
    for(; l; l=pre[l])
    {
        while(pre[r] && dis[l]-dis[pre[r]]<=s) r=pre[r];
        ans=min(ans, max(dis[rpnt]-dis[l], dis[r]));
    }
    for(int i=rpnt; i; i=pre[i]) vis[i]=true;
    for(int i=rpnt; i; i=pre[i]) dis[i]=0, dfs(i, pre[i]);
    for(int i=1; i<=n; i++) ans=max(ans, dis[i]);
}

int main()
{
    scanf("%d%d", &n, &s);
    for(int i=1; i<n; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    getline();
    solve(); 
    printf("%lld\n", ans);
}