WA+MLE求助,思路就是题解一的思路
查看原帖
WA+MLE求助,思路就是题解一的思路
823227
lightmon楼主2024/3/1 20:06

如题,没找到错误,望大佬帮忙!

#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>

// #pragma O(2)
#define int long long
// 返回x的二进制中1的个数
#define ppc(x) __builtin_popcount(x)
// 返回x的二进制中前导0的个数
#define clz(x) __builtin_clz(x)
// 返回x的二进制中后导0的个数
#define ctz(x) __builtin_ctz(x)
// lg(8) = 3, lg(16) = 4, 计算x的以2为底的对数的向下取整, 即x的最高位1的位置
#define lg(x) __lg(x)

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PDI = pair<double, int>;
using PDD = pair<double, double>;
using ULL = unsigned long long;

const int mod = 998244353;
const int N = 3e5 + 10, M = 5e5 + 10;
const int INF = (1LL << 31) - 1;
const LL LLF = 2e18 - 1;

// 用于检测程序占用内存大小
bool Mbe;

// 随机数生成器
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd(1064);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

// 取模运算
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
void subt(int &x, int y) {x -= y, x < 0 && (x += mod);}
void mult(int &x, int y) {x = (LL)x * y % mod;}
int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y;}
int sub(int x, int y) {return x - y < 0 ? x - y + mod : x - y;}
int mul(int x, int y) {return (LL)x * y % mod;}

// 快速幂
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) mult(res, a);
        mult(a, a), b >>= 1;
    }
    return res;
}

// 最大公约数
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

// 逆元
int inv(int x) {return qpow(x, mod - 2);}

// 二分
int bsearch(int l, int r, function<bool(int)> f) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (f(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 读入优化
inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    while (c < 48 || c > 57) {
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        s = (s << 1) + (s << 3) + c - 48, c = getchar();
    return s * w;
}

// 输出优化
inline void pf(LL x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) pf(x / 10);
    putchar(x % 10 + 48);
}

// 求组合数
// const int Z = 1e6 + 10;
// int fc[Z], ifc[Z];
// int bin(int n, int m) {
//     if(n < m) return 0;
//     return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
// }
// void init_fac(int Z) {
//     for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
//     ifc[Z - 1] = qpow(fc[Z - 1], mod - 2);
//     for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
// }

/* template above */

int dfn[N];
int depth[N];
int fa[N][18];
int minv[N];
int lst[N];
int query[N];
int n, q;
int cnt;
int h[N], e[N << 1], ne[N << 1], w[N << 1], idx;
int h0[N], e0[N << 1], ne0[N << 1], idx0;
int f[N];
int st[N];

void addEdge(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void addEdge(int a, int b) {
    e0[idx0] = b, ne0[idx0] = h0[a], h0[a] = idx0 ++;
}

void dfs(int u, int dep) {
    dfn[u] = ++cnt;
    depth[u] = dep;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (dfn[j]) continue;
        minv[j] = min(minv[u], w[i]);
        dfs(j, dep + 1);
        fa[j][0] = u;
        for (int k = 1; k <= 17; k ++) {
            fa[j][k] = fa[fa[j][k - 1]][k - 1];
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 17; k >= 0; k --) {
        if (depth[fa[a][k]] >= depth[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 17; k >= 0; k --) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

void dfs0(int u) {
    int sum = 0;   
    for (int i = h0[u]; ~i; i = ne0[i]) {
        int j = e0[i];
        dfs0(j);
        sum += f[j];
    }
    if (query[u]) {
        f[u] = minv[u];
    }
    else {
        f[u] = min(minv[u], sum);
    }
    // 清空虚树
    query[u] = 0;
    h0[u] = -1;
}

void solve() {
    minv[1] = LLF;
    cin >> n;
    memset(h, -1, sizeof h);
    memset(h0, -1, sizeof h0);
    for (int i = 1; i <= n - 1; i ++) {
        int x, y, z;
        cin >> x >> y >> z;
        addEdge(x, y, z), addEdge(y, x, z);
    }
    dfs(1, 1);
    // for (int i = 1; i <= n; i ++) {
    //     cout << minv[i] << ' ';
    // }
    // cout << endl;
    cin >> q;
    while (q --) {
        int k;
        cin >> k;
        for (int i = 1; i <= k; i ++) {
            cin >> lst[i];
            query[lst[i]] = 1;
        }
        sort(lst + 1, lst + 1 + k, [](int a, int b) {
            return dfn[a] < dfn[b];
        });
        int tt = 0;
        st[++tt] = lst[1];
        for (int i = 2; i <= k; i ++) {
            int now = lst[i];
            int lc = lca(now, st[tt]);
            while (1) {
                if (depth[lc] >= depth[st[tt - 1]]) {
                    if (lc != st[tt]) {
                        addEdge(lc, st[tt]);
                        if (lc != st[tt - 1]) {
                            st[tt] = lc;
                        }
                        else {
                            tt --;
                        }
                    }
                    break;
                }
                else {
                    addEdge(st[tt - 1], st[tt]);
                    tt --;
                }
            }
            st[++tt] = now;
        }
        while (--tt) {
            addEdge(st[tt], st[tt + 1]);
        }
        dfs0(st[1]);
        // cout << st[1] << endl;
        // for (int i = 1; i <= k; i ++) {
        //     cout << f[lst[i]] << ' ';
        // }
        // cout << endl;
        cout << f[st[1]] << endl;
        idx0 = 0;
    }
}

bool Med;
signed main() {
    fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) solve();
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}
2024/3/1 20:06
加载中...