E1. Weights Division (easy version)

Topic source

https://codeforces.ml/contest/1399/problem/E1

Topic meaning analysis

The meaning of the topic can be roughly described as that given a weighted root tree whose root is the point numbered 1, the sum of the distances from the root node to all leaf nodes is required to be less than the value S given by a topic. In order to achieve the goal, each time we can select an edge and divide its weight wi by 2 to round down. Ask how many operations are required at least.  

Train of thought analysis

Looking at this problem, we can realize that greed can be used to solve this problem. Regardless of the tree, we press all edges into a priority queue and take the maximum value for one operation each time.
Then the next task is how to obtain the values of these edges. It is conceivable that the weight contributed by many edges is not their own weight, because there will be many leaf nodes under a node, so the total number of times that the edge of the node connected to the parent node will no longer be 1. Here we can use a dfs to realize it, that is, in dfs, when we encounter a node every time, in the process of traversing all the edges connected to it, we can record the number of leaf nodes in the subtree with its child node as the root, that is, finally we can get the number of leaf nodes in the subtree with this node as the root, and assign this number to the edge connected to its parent node.
Finally, the number of operations is judged by traversing all edges.
Some details of the topic need to be noted. First of all, each operation is to divide the weight of the edge by 2 and round it down, rather than divide its contribution value by 2 and round it down. There is a difference between the two (it seems to be a problem of reading the topic). In addition, the sorting method in the priority queue should be to sort the keywords according to the reduction of the contribution degree of each operation, rather than directly sort by the contribution degree. Here are examples: an edge with a weight of 1 needs to pass 70 times and an edge with a weight of 10 needs to pass 8 times.

I've been there many times. I'm a real dish

code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 #include <stack>
 6 #include <set>
 7 #include <map>
 8 
 9 #define int long long
10 using namespace std;
11 const int maxn = 1e5 + 7;
12 struct edge{
13     int u, v, w, nxt, num;
14 };
15 
16 struct node{
17     int w, num;
18     node(){}
19     node(int _w, int _num):w(_w), num(_num){}
20     bool operator<(const node& a) const{
21         return w*num-(w/2)*num<a.w*a.num-(a.w/2)*a.num;
22     }
23 };
24 
25 edge e[maxn * 4];
26 int head[maxn], hcnt, in[maxn];
27 priority_queue <node> q;
28 
29 void init(){
30     memset(in, 0, sizeof (in));
31     memset(head, -1, sizeof (head));
32     hcnt = 0;
33     while (!q.empty()) q.pop();
34 }
35 
36 void adde(int u, int v, int w){
37     e[hcnt].u = u; e[hcnt].v = v; e[hcnt].w = w; e[hcnt].num = 0;
38     e[hcnt].nxt = head[u]; head[u] = hcnt ++;
39 
40     e[hcnt].u = v; e[hcnt].v = u; e[hcnt].w = w; e[hcnt].num = 0;
41     e[hcnt].nxt = head[v]; head[v] = hcnt ++;
42 }
43 
44 void dfs(int x, int f){
45     int ft = -1, nm = 0;
46     for (int i=head[x]; ~i; i=e[i].nxt){
47         int v = e[i].v, w = e[i].w;
48         if (v == f) {ft = i; continue;}
49         dfs(v, x);
50         nm += e[i^1].num;
51     }
52     if (in[x] == 1) nm ++;
53     if (ft != -1)
54         e[ft].num = nm;
55 }
56 
57 
58 
59 signed main(){
60     int t; scanf("%lld", &t);
61     while (t --){
62         init();
63         int n, s;
64         scanf("%lld%lld", &n, &s);
65         int _u, _v, _w;
66         for (int i=1; i<n; i++){
67             scanf("%lld%lld%lld", &_u, &_v, &_w);
68             adde(_u, _v, _w);
69             in[_u] ++; in[_v] ++;
70         }
71 
72         dfs(1, 0);
73         int ans = 0, sum = 0;
74         for (int i=0; i<hcnt; i++) {
75 //            printf("&& %lld  %lld %lld  \n", e[i].num, e[i].w ,e[i].num * e[i].w);
76             sum += e[i].num * e[i].w;
77             q.push(node(e[i].w , e[i].num));
78         }
79 
80         while (sum > s){
81             node h = q.top();
82             sum = sum - h.w * h.num + (h.w / 2) * h.num;
83             q.pop();
84             q.push(node(h.w / 2, h.num));
85             ans ++;
86         }
87 
88         printf("%lld\n", ans);
89     }
90     return 0;
91 }

 

Posted by dewed on Fri, 20 May 2022 09:07:37 +0300