AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 264. 权值

作者: 作者的头像   Crescent ,  2021-11-08 18:54:26 ,  所有人可见 ,  阅读 47


0


// Problem: 权值
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/266/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define pi pair<int, int>
#define vi vector<int>

using namespace std;

typedef long long LL;

template <typename T> bool chkmax(T &x, T y) { return y > x ? x = y, 1 : 0; }
template <typename T> bool chkmin(T &x, T y) { return x > y ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2e5 + 10, S = 1e6 + 10, M = N << 1, INF = N;

int n, m, h[N], e[M], w[M], ne[M], idx, f[S];
int res = INF;
bool st[N];
pi q[N], p[N];

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

void get_dist(int u, int fa, int dist, int cnt, int &qt) {
    if (st[u] || dist > m) return ;
    q[ ++ qt] = {dist, cnt};
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

int get_size(int u, int fa) {
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int &wc) {
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        chkmax(ms, t);
        sum += t;
    }
    chkmax(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void calc(int u) {
    if (st[u]) return ;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i], qt = 0;
        get_dist(j, u, w[i], 1, qt);
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            if (t.fi == m) chkmin(res, t.se);
            chkmin(res, t.se + f[m - t.fi]);
            p[ ++ pt] = t;
        }
        for (int k = 1; k <= qt; k ++ ) {
            auto& t = q[k];
            chkmin(f[t.fi], t.se);
        }
    }
    //回溯
    for (int i = 1; i <= pt; i ++ )
        f[p[i].fi] = INF;   
    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}


int main() {
    //f[i]=j表示距离重心长度为i的点最少经过j条边到达
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b, c; read(a), read(b), read(c);
        add(a, b, c), add(b, a, c);
    }
    memset(f, 0x3f, sizeof f);
    calc(1);
    if (res == INF) res = -1;
    cout << res;
    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息