> If you have a brute force solution runs 10 seconds, but time limit is 2 seconds, **stop thinking the correct solution, go to optimize your brute force solution.**↵
↵
Problem: https://qoj.ac/problem/8616↵
↵
This problem is weird: it requires tree path addition and tree path XOR sum queries. ↵
↵
If the queries were on a sequence rather than a tree, use [this](https://codeforces.me/blog/entry/148180) approach and you will get an $O(q\sqrt{n}\log n\log V)$ solution. By combining this with heavy-light decomposition, we can solve the tree version in $O(q\sqrt{n} \log^2 n\log V)$ time with a high constant factor, **cannot pass the time limit**. It's even slower than brute force under these constraints!↵
↵
Now we think of brute force.↵
↵
The basic brute force approach is, for two nodes $u$ and $v$, find their LCA, and move both $u,v$ upward toward their LCA, update all the elements on the path. This is slow, isn't it? On modern computers, contiguous memory access is faster than random memory access. So we can use heavy-light decomposition to turn the random accesses into $O(\log n)$ contiguous segments. Then, with `#pragma GCC optimize("O3,unroll-loops")` and `#pragma GCC target("avx2,sse4.2,avx512f")`, so you can get accepted on this problem.↵
↵
Try it! https://qoj.ac/problem/8616
↵
Problem: https://qoj.ac/problem/8616↵
↵
This problem is weird: it requires tree path addition and tree path XOR sum queries. ↵
↵
If the queries were on a sequence rather than a tree, use [this](https://codeforces.me/blog/entry/148180) approach and you will get an $O(q\sqrt{n}\log n\log V)$ solution. By combining this with heavy-light decomposition, we can solve the tree version in $O(q\sqrt{n} \log^2 n\log V)$ time with a high constant factor, **cannot pass the time limit**. It's even slower than brute force under these constraints!↵
↵
Now we think of brute force.↵
↵
The basic brute force approach is, for two nodes $u$ and $v$, find their LCA, and move both $u,v$ upward toward their LCA, update all the elements on the path. This is slow, isn't it? On modern computers, contiguous memory access is faster than random memory access. So we can use heavy-light decomposition to turn the random accesses into $O(\log n)$ contiguous segments. Then, with `#pragma GCC optimize("O3,unroll-loops")` and `#pragma GCC target("avx2,sse4.2,avx512f")`, so you can get accepted on this problem.↵
↵
Try it! https://qoj.ac/problem/8616
