MLE 50pts 求调 码风优良
查看原帖
MLE 50pts 求调 码风优良
374347
Wander_E楼主2024/8/17 11:28
#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int N = 5e5 + 500;
const long long INF = 0x7f7f7f7f7f7f7f7f;
int n, m, k;
int a[N << 1];
int h[N], ne[N], to[N], w[N], id;
int dfn[N], st[64][N], lg[N], idl[N], dep[N], tim, idx;
long long minv[N];
bool query[N];
vector<int> g[N];
void add(int x, int y, int z)
{
    to[++id] = y, ne[id] = h[x], w[id] = z, h[x] = id;
    to[++id] = x, ne[id] = h[y], w[id] = z, h[y] = id;
}

void dfs(int u, int fa)
{
    dfn[u] = ++tim;
    st[0][++idx] = u;
    idl[u] = idx;
    dep[u] = dep[fa] + 1;
    for (int i = h[u]; i; i = ne[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        minv[v] = min(minv[u], 1ll * w[i]);
        dfs(v, u);
        st[0][++idx] = u;
    }
}

int lower(int x, int y)
{
    return dep[x] < dep[y] ? x : y;
}
bool cmp(int x, int y)
{
    return dfn[x] < dfn[y];
}

void getst()
{
    for (int i = 2; i <= idx; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; (1 << i) <= idx; i++)
    {
        int w = (1 << i);
        for (int j = 1; j + w - 1 <= idx; j++)
        {
            st[i][j] = lower(st[i - 1][j], st[i - 1][j + w / 2]);
        }
    }
}

int lca(int x, int y)
{
    x = idl[x], y = idl[y];
    if (x > y)
        swap(x, y);
    int len = lg[y - x + 1];
    return lower(st[len][x], st[len][y - (1 << len) + 1]);
}
void build(int &root)
{
    root = a[1];
    int tot = k;
    sort(a + 1, a + tot + 1, cmp);
    for (int i = 2; i <= k; i++)
    {
        int lc = lca(a[i], a[i - 1]);
        if (lc != a[i] && lc != a[i - 1])
            a[++tot] = lc;
    }
    tot = unique(a + 1, a + tot + 1) - (a + 1);
    sort(a + 1, a + tot + 1, cmp);
    for (int i = 2; i <= tot; i++)
    {
        int lc = lca(a[i], a[i - 1]);
        g[lc].push_back(a[i]);
        if (dep[lc] < root)
            root = lc;
    }
}

long long solve(int u)
{
    long long sum = 0;
    long long tmp;
    for (auto v : g[u])
        sum += solve(v);
    if (query[u])
        tmp = minv[u];
    else
        tmp = min(minv[u], sum);
    query[u] = false;
    g[u].clear();
    return tmp;
}
signed main()
{
    minv[1] = INF;
    cin >> n;
    for (int i = 1, x, y, z; i < n; i++)
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }
    dfs(1, 0);
    getst();
    cin >> m;
    while (m--)
    {
        cin >> k;
        for (int i = 1; i <= k; i++)
        {
            cin >> a[i];
            query[a[i]] = 1;
        }
        int rt;
        build(rt);
        cout << solve(rt) << endl;
    }
    return 0;
}
2024/8/17 11:28
加载中...