大臣的旅费 四届c++ A T10

题意：

给定一棵树，求直径

思考：

方法一

BFS。先任取一点，跑一遍bfs找到距离最大的点，再对距离最大的那个点作为起点，跑一遍bfs，就能找到直径了。

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
typedef long long LL;
vector<PII> mp[N];
int n,p,q,d,dis[N];
bool st[N];
LL ans,idx;
void bfs(int u){
    memset(dis,0x3f,sizeof dis);
    memset(st,0,sizeof st);
    queue<int> qu;
    st[u]= true;
    qu.push(u);
    dis[u]=0;
    ans=dis[u];
    idx=u;
    while(!qu.empty()){
        int tp=qu.front();
        qu.pop();
        for(auto pi:mp[tp]){
            if(st[pi.second]) continue;
            dis[pi.second]=dis[tp]+pi.first;
            if(dis[pi.second]>ans){
                idx=pi.second;
                ans=dis[pi.second];
            }
            qu.push(pi.second);
            st[pi.second]=true;
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&p,&q,&d);
        mp[p].push_back({d,q});
        mp[q].push_back({d,p});
    }
    bfs(1);
    bfs(idx);
    cout<<ans*10+(ans+1)*ans/2;
    return 0;
}

技巧总结：以前蓝桥杯的题是真的简单（还是最后一题hh）

方法二

树形dp。从任意结点开始，找到每个结点且经过该节点向下走的最大长度d1和次大长度d2，则经过该节点的最大长度是d1 + d2

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
typedef long long LL;
vector<PII> mp[N];
LL n,p,q,d,dis[N];
bool st[N];
LL ans,idx;
void dp(int u){
    st[u]= true;
    for(auto tp:mp[u]){
        if(st[tp.second]) continue;
        dp(tp.second);
        ans=max(ans,dis[u]+dis[tp.second]+tp.first);
        dis[u] = max(dis[u],dis[tp.second]+tp.first);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        scanf("%lld%lld%lld",&p,&q,&d);
        mp[p].push_back({d,q});
        mp[q].push_back({d,p});
    }
    dp(1);
    cout<<ans*10+(ans+1)*ans/2;
    return 0;
}