Frames

Untitled

0
1// #include <cmath>
2// #include <cstdio>
3// #include <iterator>
4// #include <vector>
5// #include <iostream>
6// #include <algorithm>
7// #include <unordered_map>
8// #include <tuple>
9// #include <string>
10// using namespace std;
11
12// //https://stackoverflow.com/questions/20834838/using-tuple-in-unordered-map
13// //https://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way
14// using cantor_pairing_key_t = std::tuple<int, int>;
15// struct cantor_pairing_hash
16// : public std::unary_function<cantor_pairing_key_t, long long>
17// {
18// long long operator()(const cantor_pairing_key_t& k) const
19// {
20// long long a = std::get<0>(k);
21// long long b = std::get<1>(k);
22// return (a + b) * (a + b + 1) / 2 + a;
23// }
24// };
25
26// struct treeNode
27// {
28// long value;
29// int children;
30// std::vector<int> path;
31// treeNode* parent;
32
33// treeNode(long v, treeNode* p) : value{v}, parent{p}, children{0}
34// {
35// if(parent == nullptr)
36// path = {};
37// else
38// {
39// //avoid extra allocation
40// path = std::vector<int>(parent->path.size() + 1);
41// path = parent->path;
42// path.push_back(parent->children);
43// ++parent->children;
44// }
45// }
46// };
47
48// long long cachehit = 0;
49// long long cachetry = 0;
50
51// struct tree
52// {
53// treeNode* root;
54// std::unordered_map<long, treeNode*> nodes;
55// std::unordered_map<std::tuple<long,long>, long, cantor_pairing_hash> distCache;
56
57// tree(size_t n) : root {nullptr}, nodes (n)
58// {
59
60// }
61
62// treeNode* find(long v)
63// {
64// auto r = nodes.find(v);
65// if (r != nodes.end())
66// return r->second;
67// else
68// return nullptr;
69// }
70
71// treeNode* setRoot(treeNode* node)
72// {
73// root = node;
74// nodes[node->value] = node;
75// return node;
76// }
77
78// treeNode* addNode(treeNode* node)
79// {
80// nodes[node->value] = node;
81// return node;
82// }
83
84// long distPaths(const std::vector<int>& a, const std::vector<int>& b)
85// {
86// auto asize = a.size();
87// auto bsize = b.size();
88// int i = 0;
89// while((i < asize) && (i < bsize) && (a[i] == b[i]))
90// ++i;
91
92// auto distance = (asize - i) + (bsize - i);
93// return distance;
94// }
95
96// long dist(treeNode* a, treeNode* b)
97// {
98// if(a == b) return 0;
99
100// ++cachetry;
101
102// auto bigger = std::max(a->value, b->value);
103// auto smaller = std::min(a->value, b->value);
104// auto key = std::make_tuple(bigger,smaller);
105
106// auto it = distCache.find(key);
107// if(it != distCache.end())
108// {
109// ++cachehit;
110// return it->second;
111// }
112
113// auto dist = distPaths(a->path, b->path);
114
115// distCache[key] = dist;
116
117// return dist;
118// }
119// };
120
121// #include <chrono>
122
123// class Fps
124// {
125// protected:
126// unsigned int m_fps;
127// unsigned int m_fpscount;
128// std::chrono::duration<double, std::milli> delta;
129// std::chrono::system_clock::time_point lastFrame;
130
131// public:
132// // Constructor
133// Fps() : m_fps(0), m_fpscount(0)
134// {
135// delta = 0ms;
136// lastFrame = std::chrono::system_clock::now();
137// }
138
139// void inc()
140// {
141// m_fpscount++;
142// }
143
144// // Update
145// bool update()
146// {
147// // increase the counter by one
148// m_fpscount++;
149
150// std::chrono::system_clock::time_point now = std::chrono::system_clock::now();
151// std::chrono::duration<double, std::milli> delta2 = now - lastFrame;
152// delta += delta2;
153// if (delta.count() >= 1000)
154// {
155// m_fps = m_fpscount;
156// m_fpscount = 0;
157// delta -= 1000ms;
158// lastFrame = now;
159// return true;
160// }
161// else
162// {
163// lastFrame = now;
164// return false;
165// }
166// }
167
168// // Get fps
169// unsigned int get() const
170// {
171// return m_fps;
172// }
173// };
174
175
176
177// int main() {
178// size_t n, q;
179// std::cin >> n >> q;
180
181// tree t {3*n};
182// for(int i = 0;i < n - 1; ++i)
183// {
184// long a,b;
185// std::cin >> a >> b ;
186
187// auto* nodea = t.find(a);
188// auto* nodeb = t.find(b);
189// if(nodea == nullptr && nodeb == nullptr)
190// {
191// nodea = t.setRoot(new treeNode{a, nullptr});
192// t.addNode(new treeNode{b, nodea});
193// }
194// else if(nodea == nullptr && nodeb != nullptr)
195// t.addNode(new treeNode{a, nodeb});
196// else if(nodeb == nullptr && nodea != nullptr)
197// t.addNode(new treeNode{b, nodea});
198// }
199
200// Fps fps;
201// std::vector<treeNode*> nodes (1000);
202// for(long i = 0;i < q; ++i)
203// {
204// size_t set_size;
205// std::cin >> set_size;
206
207// if(set_size <= 1)
208// {
209// long noden;
210// std::cin >> noden;
211// std::cout << 0 << std::endl;
212// }
213// else {
214// nodes.clear();
215// for(int inode = 0;inode < set_size; ++inode)
216// {
217// long noden;
218// std::cin >> noden;
219// nodes.push_back(t.find(noden));
220// }
221
222
223
224// long accum = 0;
225// long modC = 1000000000 + 7;
226// long long fpsi = 0;
227// for(long pairstart = 0;pairstart < nodes.size(); ++pairstart)
228// {
229// auto nodestart = nodes[pairstart];
230// for(long pairend = pairstart + 1;pairend < nodes.size(); ++pairend)
231// {
232// // ++fpsi;
233// // fps.inc();
234
235// // if((fpsi % 1000 == 0) && fps.update())
236// // std::cout << "fps: " << fps.get() << std::endl;
237
238// auto nodeend = nodes[pairend];
239// auto dist = t.dist(nodestart, nodeend);
240
241// // //https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication
242// // //https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction
243// long accum_term = (nodestart->value * nodeend->value * dist);
244// accum += accum_term;
245// // accum %= modC;
246// }
247// }
248// std::cout << accum % modC << std::endl;
249// }
250
251// std::cout << "cache try" << cachetry << std::endl;
252// std::cout << "cache hit" << cachehit << std::endl;
253// }
254
255// return 0;
256// }
257
258#define _CRT_SECURE_NO_WARNINGS
259
260
261#include <iostream>
262#include <cstdio>
263#include <vector>
264#include <cstring>
265#include <utility>
266#include <algorithm>
267using namespace std;
268
269using pii = pair<int64_t,int64_t>;
270const int MAX_N = 2e5 + 6;
271const int MAX_P = 19;
272const int64_t mod = 1e9 + 7;
273
274vector<int> childrens[MAX_N];
275int distance_to_node[MAX_P][MAX_N];
276bool visited[MAX_N];
277
278struct centroid_node {
279 int parent;
280 int depth;
281 pii val_v_av; //first --> val, second --> minus
282 pii val_v;
283
284 int64_t VALUE;
285} centroids[MAX_N];
286
287pii operator+(const pii& p1, const pii& p2) {
288 return make_pair(p1.first + p2.first, p1.second + p2.second);
289}
290
291pii operator-(const pii& p1, const pii& p2) {
292 return make_pair(p1.first - p2.first, p1.second - p2.second);
293}
294
295pii operator+=(pii& p1, const pii& p2) {
296 p1 = p1 + p2;
297 return p1;
298}
299
300pii operator-=(pii& p1, const pii& p2) {
301 p1 = p1 - p2;
302 return p1;
303}
304
305void Pure(pii& p)
306{
307 p.first = (p.first % mod + mod) % mod;
308 p.second = (p.second % mod + mod) % mod;
309}
310
311void dotNode(int p, const std::string& color)
312{
313 auto& cp = centroids[p];
314 std::cout << p << "[label=\"" << p
315 << ",value=" << cp.val_v.first
316 << ",minus=" << cp.val_v.second
317 << ",value=" << cp.val_v_av.first
318 << ",minus=" << cp.val_v_av.second
319 << ",NODEVALUE=" << cp.VALUE
320 << "\", color = \"" << color << "\"]" << std::endl;
321}
322
323
324struct centroid_decomposition
325{
326 vector<int> vertices;
327 int qtd_descendents[MAX_N];
328
329 int get_centroid_of(int id)
330 {
331 auto& descendents = vertices;
332
333 descendents.clear();
334 find_descendents(id);
335 int qtd_my_descendents = descendents.size();
336 int centroid_threshold = qtd_my_descendents / 2;
337
338 int centroid = -1;
339 for (int i : descendents)
340 {
341 if (max(0, qtd_my_descendents - qtd_descendents[i]) <= centroid_threshold)
342 {
343 centroid = i;
344 }
345 visited[i] = false;
346 }
347 return centroid;
348 }
349
350 void run(int id, int parent_in_centroid_tree, int depth_in_centroid_tree)
351 {
352 int id_in_centroid_tree = get_centroid_of(id);
353
354 update_distances(id_in_centroid_tree, id_in_centroid_tree, depth_in_centroid_tree, 0);
355
356 centroids[id_in_centroid_tree] =
357 {
358 parent_in_centroid_tree,
359 depth_in_centroid_tree,
360 {0,0},
361 {0,0}
362 };
363 visited[id_in_centroid_tree] = true;
364
365 for (int i : childrens[id_in_centroid_tree])
366 {
367 if (!visited[i])
368 run(i, id_in_centroid_tree, depth_in_centroid_tree + 1);
369 }
370 }
371
372 void broadcast_value(int64_t x)
373 {
374 int64_t p = x;
375
376 while (p != -1)
377 {
378 auto& cp = centroids[p];
379
380 dotNode(p, "red");
381 std::cout << "label = \"broadcast_value "
382 << x
383 << " x: " << x
384 << ", depth: " << cp.depth
385 << ", dist: " << distance_to_node[cp.depth][x]
386 << "\""
387 << std::endl;
388
389 cp.val_v += {x, 0};
390 cp.val_v_av += {x * distance_to_node[cp.depth][x], 0};
391
392 cp.VALUE += x;
393 dotNode(p, "green");
394
395 if (cp.parent != -1)
396 {
397 int par = cp.parent;
398 auto& cpar = centroids[par];
399
400 std::cout << "label = \"broadcast_value "
401 << x
402 << " (parent) x: " << x
403 << ", depth: " << cpar.depth
404 << ", dist: " << distance_to_node[cpar.depth][x]
405 << "\""
406 << std::endl;
407 cp.val_v -= {0, x};
408 cp.val_v_av -= {0, x * distance_to_node[cpar.depth][x]};
409 }
410
411 //Pure(cp.val_v);
412 //Pure(cp.val_v_av);
413
414 dotNode(p, "black");
415
416 p = cp.parent;
417 }
418 }
419
420 void remove_value(int64_t x)
421 {
422 int64_t p = x;
423
424 while (p != -1)
425 {
426 dotNode(p, "red");
427
428 auto& cp = centroids[p];
429
430 cp.val_v -= {x, 0};
431 cp.val_v_av -= {x* distance_to_node[cp.depth][x], 0};
432
433 cp.VALUE -= x;
434
435 if (centroids[p].parent != -1)
436 {
437 int par = cp.parent;
438 auto& cpar = centroids[par];
439
440 cp.val_v += {0, x};
441 cp.val_v_av += {0, x* distance_to_node[cpar.depth][x]};
442 }
443
444 //Pure(centroids[p].val_v);
445 //Pure(centroids[p].val_v_av);
446 p = centroids[p].parent;
447
448 dotNode(p, "black");
449 }
450 }
451
452 void dotQuery(int64_t x, int64_t p, int64_t ret, int64_t v, int64_t v_av, const std::string& op)
453 {
454 auto& cp = centroids[p];
455 std::cout << "label = \"query " << x <<
456 " ret=" << ret <<
457 " v=" << v <<
458 " v_av=" << v_av <<
459 "distance to " << x << "=" << distance_to_node[cp.depth][x] <<
460 op <<
461 "\"" << std::endl;
462 }
463
464 int64_t query(int64_t x)
465 {
466 int64_t ret = 0;
467 int64_t v = 0;
468 int64_t v_av = 0;
469 int p = x;
470
471 while (p != -1)
472 {
473 auto& cp = centroids[p];
474
475 v += cp.val_v.first;
476 v_av += cp.val_v_av.first;
477 ret += x * v_av;
478 //ret %= mod;
479 ret += x * distance_to_node[cp.depth][x] * v;
480 //ret %= mod;
481 v = cp.val_v.second;
482 v_av = cp.val_v_av.second;
483
484 p = cp.parent;
485 }
486
487 return ret;
488 }
489private:
490 void find_descendents(int id)
491 {
492 vertices.push_back(id);
493 visited[id] = true;
494 qtd_descendents[id] = 1;
495
496 for (int i : childrens[id])
497 {
498 if (!visited[i])
499 {
500 find_descendents(i);
501 qtd_descendents[id] += qtd_descendents[i];
502 }
503 }
504 }
505
506 void update_distances(int id, int parent, int cen_depth, int dist)
507 {
508 distance_to_node[cen_depth][id] = dist;
509 for (int i : childrens[id])
510 {
511 if (!visited[i] && i != parent)
512 {
513 update_distances(i, id, cen_depth, dist + 1);
514 }
515 }
516 }
517};
518
519
520int64_t pow(int64_t a,int64_t n,int64_t mod)
521{
522 if (n==0) return 1;
523 else if (n==1) return a;
524 int64_t ret=pow(a,n/2,mod);
525 ret*=ret;
526 ret%=mod;
527 if (n&1) {
528 ret*=a;
529 ret%=mod;
530 }
531 return ret;
532}
533
534void generateDOT(int n)
535{
536 while (n >= 0)
537 {
538 for (int i : childrens[n])
539 {
540 std::cout << n << "->" << i << ";" << std::endl;
541 }
542 --n;
543 }
544}
545
546void generateCentroidDOT(int n)
547{
548 while(n >= 0)
549 {
550 auto& c = centroids[n];
551 if(c.parent != -1)
552 std::cout << n << "->" << c.parent << "[color=\"brown\"];" << std::endl;
553 else
554 dotNode(n, "brown");
555 --n;
556 }
557}
558
559int main () {
560 int n, q;
561 std::cin >> n >> q;
562
563 int maxnode = 0;
564 for (int i = 1;i <= n-1; ++i)
565 {
566 int a,b;
567 std::cin >> a >> b;
568
569 childrens[a].push_back(b);
570 childrens[b].push_back(a);
571
572 maxnode = std::max(a, maxnode);
573 maxnode = std::max(b, maxnode);
574 }
575
576 generateDOT(maxnode);
577
578 auto cd = new centroid_decomposition{};
579 cd->run(1, -1, 0);
580
581 generateCentroidDOT(maxnode);
582
583 while (q--)
584 {
585 int k;
586 std::cin >> k;
587
588 vector<int> set_nodes;
589 while (k--)
590 {
591 int x;
592 std::cin >> x;
593 set_nodes.push_back(x);
594 }
595
596 for (int i : set_nodes)
597 dotNode(i, "green");
598
599 for (int i : set_nodes)
600 {
601 std::cout << "label = \"broadcast_value " << i << "\"" << std::endl;
602 cd->broadcast_value(i);
603 }
604
605 int64_t value = 0;
606 for (int i : set_nodes)
607 {
608 std::cout << "label = \"query " << i << "\"" << std::endl;
609 value += cd->query(i);
610 value %= mod;
611 }
612
613 for (int i : set_nodes)
614 {
615 std::cout << "label = \"remove_value " << i << "\"" << std::endl;
616 cd->remove_value(i);
617 }
618
619 //std::cout << (value * pow(2, mod - 2, mod) + mod) % mod << std::endl;
620 }
621}
622