1.【題目鏈接】https://www.luogu.com.cn/problem/P4149

題目描述

給一棵樹，每條邊有權(quán)。求一條簡單路徑，權(quán)值和等于?K，且邊的數(shù)量最小。

輸入格式

第一行包含兩個整數(shù)?n, K。

接下來?n - 1 行，每行包含三個整數(shù)，表示一條無向邊的兩端和權(quán)值。

注意點的編號從?0?開始。

輸出格式

輸出一個整數(shù)，表示最小邊數(shù)量。

如果不存在這樣的路徑，輸出?-1。

輸入輸出樣例

輸入 #1復制

4 3
0 1 1
1 2 2
1 3 4

輸出 #1復制

2

說明/提示

保證?n?2× 10^5 ,?K? 10^6 。

2.題意：

給一棵樹,每條邊有權(quán).求一條簡單路徑,權(quán)值和等于K,且邊的數(shù)量最小.N <= 200000, K <= 1000000

3.思路

明顯點分治，但是愚蠢的我并沒有想到怎么分治。。。

開一個t[i]表示整棵樹中權(quán)值和為i的路徑有多少條，那么我們分治每一顆樹的時候，再算出子節(jié)點到當前根的dis[x]權(quán)值距離和d[x]點數(shù)距離，然后就可以直接更新了ans=min(ans,t[k-dis[x]]+d[x]);

然后再更新dis和d，因為如果先更新了就會算重，有一種情況，即起點終點在子樹內(nèi)但是經(jīng)過了根，這樣就會算重復了。。

注意INF設(shè)小一點，不然會爆int。。

4.Code

//Happynewyear 2019/1/23 20:24
#include<bits/stdc++.h> ? ? ?//萬能頭文件

const int MAXN = 200000;
const int MAXK = 1000000;

struct Node;
struct Edge;

struct Node {
? ?Edge *e;
? ?int dist, depth, size, max;
? ?bool visited, solved;
? ?Node *parent;
} N[MAXN];

struct Edge {
? ?Node *s, *t;
? ?int w;
? ?Edge *next;

? ?Edge(Node *s, Node *t, const int w) : s(s), t(t), w(w), next(s->e) {}
};

inline void addEdge(const int s, const int t, const int w) {
? ?N[s].e = new Edge(&N[s], &N[t], w);
? ?N[t].e = new Edge(&N[t], &N[s], w);
}

int n, k;
int f[MAXK + 1];

inline Node *center(Node *start) {
? ?std::stack<Node *> s;
? ?s.push(start);
? ?start->parent = NULL;
? ?start->visited = false;

? ?static Node *a[MAXN];
? ?int cnt = 0;
? ?while (!s.empty()) {
? ? ? ?Node *v = s.top();
? ? ? ?if (!v->visited) {
? ? ? ? ? ?v->visited = true;
? ? ? ? ? ?a[cnt++] = v;
? ? ? ? ? ?for (Edge *e = v->e; e; e = e->next) if (!e->t->solved && e->t != v->parent) {
? ? ? ? ? ? ? ?e->t->parent = v;
? ? ? ? ? ? ? ?e->t->visited = false;
? ? ? ? ? ? ? ?s.push(e->t);
? ? ? ? ? ?}
? ? ? ?} else {
? ? ? ? ? ?v->size = 1;
? ? ? ? ? ?v->max = 0;
? ? ? ? ? ?for (Edge *e = v->e; e; e = e->next) if (!e->t->solved && e->t->parent == v) {
? ? ? ? ? ? ? ?v->size += e->t->size;
? ? ? ? ? ? ? ?v->max = std::max(v->max, e->t->size);
? ? ? ? ? ?}
? ? ? ? ? ?s.pop();
? ? ? ?}
? ?}


? ?Node *res = NULL;
? ?for (int i = 0; i < cnt; i++) {
? ? ? ?assert(cnt == start->size);
? ? ? ?a[i]->max = std::max(a[i]->max, cnt - a[i]->size);
? ? ? ?if (!res || res->max > a[i]->max) res = a[i];
? ?}
? ?return res;
}

inline int calc(Node *root) {
? ?static int A[MAXN];
? ?int tot = 0, res = INT_MAX;
? ?for (Edge *e = root->e; e; e = e->next) if (!e->t->solved) {
? ? ? ?std::queue<Node *> q;
? ? ? ?q.push(e->t);
? ? ? ?e->t->parent = root;
? ? ? ?e->t->dist = e->w;
? ? ? ?e->t->depth = 1;

? ? ? ?static Node *a[MAXN];
? ? ? ?int cnt = 0;
? ? ? ?while (!q.empty()) {
? ? ? ? ? ?Node *v = q.front();
? ? ? ? ? ?q.pop();

? ? ? ? ? ?if (v->dist > k) continue;

? ? ? ? ? ?A[tot++] = v->dist;
? ? ? ? ? ?a[cnt++] = v;

? ? ? ? ? ?for (Edge *e = v->e; e; e = e->next) if (!e->t->solved && e->t != v->parent) {
? ? ? ? ? ? ? ?e->t->parent = v;
? ? ? ? ? ? ? ?e->t->dist = v->dist + e->w;
? ? ? ? ? ? ? ?e->t->depth = v->depth + 1;
? ? ? ? ? ? ? ?q.push(e->t);
? ? ? ? ? ?}
? ? ? ?}

? ? ? ?for (int i = 0; i < cnt; i++) {
? ? ? ? ? ?if (f[k - a[i]->dist] != INT_MAX) res = std::min(res, f[k - a[i]->dist] + a[i]->depth);
? ? ? ?}

? ? ? ?for (int i = 0; i < cnt; i++) {
? ? ? ? ? ?f[a[i]->dist] = std::min(f[a[i]->dist], a[i]->depth);
? ? ? ?}
? ?}

? ?for (int i = 0; i < tot; i++) {
? ? ? ?f[A[i]] = INT_MAX;
? ?}
? ?return res;
}

inline int solve() {
? ?std::stack<Node *> s;
? ?s.push(&N[0]);

? ?int ans = INT_MAX;
? ?while (!s.empty()) {
? ? ? ?Node *v = s.top();
? ? ? ?s.pop();

? ? ? ?Node *root = center(v);
? ? ? ?root->solved = true;

? ? ? ?ans = std::min(ans, calc(root));

? ? ? ?for (Edge *e = root->e; e; e = e->next) if (!e->t->solved) {
? ? ? ? ? ?s.push(e->t);
? ? ? ?}
? ?}

? ?return ans;
}

int main() {
? ?scanf("%d %d", &n, &k); ? ? //輸入

? ?for (int i = 0; i < n - 1; i++) { ? ?//for循環(huán)
? ? ? ?int u, v, w;
? ? ? ?scanf("%d %d %d", &u, &v, &w); ? //輸入
? ? ? ?addEdge(u, v, w);
? ?}

? ?for (int i = 1; i <= k; i++) f[i] = INT_MAX;

? ?int ans = solve();
? ?printf("%d\n", ans == INT_MAX ? -1 : ans); ? ?//輸出

? ?return 0; ? ? ? ? //不寫return 0,成績return 0
}

提交記錄 in 2019-10-10