1.【题目链接】https://www.luogu.com.cn/problem/P4149

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 K，且边的数量最小。

输入格式

第一行包含两个整数 n, K。

接下来 n - 1 行，每行包含三个整数，表示一条无向边的两端和权值。

注意点的编号从 0 开始。

输出格式

输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 -1。

输入输出样例

输入 #1复制

4 3
0 1 1
1 2 2
1 3 4

输出 #1复制

2

说明/提示

保证 n⩽2× 10^5 , K⩽ 10^6 。

2.题意：

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

3.思路

明显点分治，但是愚蠢的我并没有想到怎么分治。。。

开一个t[i]表示整棵树中权值和为i的路径有多少条，那么我们分治每一颗树的时候，再算出子节点到当前根的dis[x]权值距离和d[x]点数距离，然后就可以直接更新了ans=min(ans,t[k-dis[x]]+d[x]);

然后再更新dis和d，因为如果先更新了就会算重，有一种情况，即起点终点在子树内但是经过了根，这样就会算重复了。。

注意INF设小一点，不然会爆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循环
       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