Hướng dẫn giải của Bedao Regular Contest 02 - TOURIST


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Ta dựng cây gốc ~A~, gọi các đỉnh trên đường đi từ ~A~ đến ~B~ lần lượt là ~u_1~, ~u_2~, ~\dots~ , ~u_k~

Ta thấy đáp án tối ưu sẽ có đường đi của ~A~ là từ ~A~ đến ~u_i~, rồi đi tiếp xuống một nhánh khác nhánh chứa đỉnh ~B~ và nhánh đó chứa nút lá có độ sâu lớn nhất trong số các nhánh anh em của nhánh chứa đỉnh ~B~, còn ~B~ sẽ đi trong cây con của ~u_{i+1}~

Gọi ~dp_u~ là kết quả tối ưu của ~B~ khi đi trong cây con gốc ~u~.

Gọi ~deep_u~ là khoảng cách xa nhất từ ~u~ đến một nút lá trong cây con gốc ~u~

Gọi ~h_u~ là độ sâu của nút ~u~ trên cây

Gọi ~ma_u~ là ~deep_v~ lớn nhất trong các ~v~ là con của ~u~ nhưng không phải là ~u_i~ nào đó

Ta có công thức tính ~dp_{u_i}~ như sau:

  • ~dp_{u_i} = deep_{u_i} + 1~ ( Nếu ~u_i = B~ )
  • ~dp_{u_i} = max(dp_{u_{i+1}}, h_B − h_u + ma_u + 1)~ ( Nếu ~ui \neq B~ )

Và với mỗi đỉnh ~u_1~, ~u_2~, ~\dots~, ~u_{k−1}~ ta cập nhập ~ans~ thành: ~max(ans,min(dp_u, h_u + ma_u + 1))~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 2E5;
const int INF = 2E9;

bool visited[N+9];
vector<int> adj[N+9];
int nodeA, nodeB;
vector<int> pathNode;
int f[N+9];
int high[N+9];
int n;

bool maximize(int &x, int y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
return false;
}

void pathCreate(int u, int p)
{
    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if (v == p) continue;

        pathCreate(v, u);

        visited[u] |= visited[v];
    }

    if (visited[u] == 1) pathNode.push_back(u);
}

void dfsUp(int u,int p)
{
    f[u] = 1;
    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if (v == p) continue;
        high[v] = high[u] + 1;

        dfsUp(v, u);

        if (visited[v] == 1) continue;
        maximize(f[u], f[v] + 1);
    }
}

int main()
{
    if (fopen(name".INP","r"))
        freopen(name".INP","r",stdin),
        freopen(name".OUT","w",stdout);

    fastIO

    cin>>n;

    for (int i = 1;i < n;++i)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cin>>nodeA>>nodeB;

    visited[nodeB] = 1;
    high[nodeA] = 1;

    pathCreate(nodeA,nodeA);
    dfsUp(nodeA, nodeA);

    reverse(pathNode.begin(),pathNode.end());

    int res = -INF;

    int distA = 0, distB = 0;
    for (int i = 0;i+1 < (int)pathNode.size(); ++i)
    {
        int u = pathNode[i];
        int v = pathNode[i+1];
        distA = max(distA, high[u] - high[nodeA] + f[u]);
        distB = high[nodeB] - high[v] + f[v];
        maximize(res, min(distA, distB));
    }

    cout<<res;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.