Auto comment: topic has been updated by LeoPro (previous revision, new revision, compare).

The memory also increased (1.5x times), it is also kinda suspicious because I haven't used any pointers.

You implicitly use pointers when you use recursion (for pushing return addresses and temporary variables onto the stack, and &tree, &minus, &right are pointers).

Just a note, I think that allocating vectors in for loops is very slow. For a heavily composite number + 1 as n, you allocate $$$2*128*n = 256n \leq 768e5 \approx 7e7$$$, which sounds really excessive. My hunch didn't translate well when I submitted with changing doing this allocation outside the loop, but I think this is a problem, even if not the cause for this timing issue.

GCC 7.3 is so cool that it's able to inline (unroll) your DFS somehow, probably partially. While GCC 9.2 can't do that :(

How to construct the slowest testcase for this problem? Just a random tree doesn't seem to be good enough.

I had the opposite experience in round 714. For problem C I made 3 submissions(all TLE 1000ms) with GNU C++17 compiler and 2 submission(545ms and 654 ms) with GNU C++17 (64) compiler.

First two submissions were inefficient and TLEd. After improving it further it still TLEd on pretest 1. Then I submitted the same code in GNU C++17 (64) compiler and surprisingly it did not TLE and gave WA on pretest 3. Changed the ans variable from int to long long and I got AC.

My submissions ran twice as fast in GNU C++17 (64) compiler. Since that day I always submit in 64 bit compiler.

The following update to your code has slight improvement in the execution time when compiled using GNU G++17 9.2.0 (64-bit). The same update compiled using GNU G++17 7.3.0 is slower than your code, even though it is still faster than the former execution time.

128493289

128493370

I tried to use int_fast32_t instead of int, but it seems even slower. https://mirror.codeforces.com/contest/1554/submission/128509324

On the subject of vector<bool>. Instead of switching it out with vector<int>, try using something like vector<char>. It cuts down your time in C++17(32 bit) to 950 ms 128678604.

Thanks to helpful comments from dalex and oversolver, I finally managed to construct a reasonably good testcase generator:

def gen_testcase(n)
  puts n
  nodes = (1 .. n).to_a.shuffle
  edges = []
  1.upto(n - 1) {|i| edges.push([nodes[i - 1], nodes[i]]) }
  edges.shuffle.each {|edge| puts "#{edge[0]} #{edge[1]}" }
end

t = 3
puts t
t.times do
  srand(957)
  gen_testcase(98280 + 1)
end

Yes, randomly shuffling nodes before connecting them in a line and then randomly shuffling edges in the input data indeed does the job. And picking the right $$$n$$$ value to maximize the number of divisors was important too. The choice of seed for randomization makes a very big difference, resulting in times between ~300ms and ~3500ms on my computer. Using one of the worst performing testcases, profiling results for the original LeoPro's solution from this blog now look like this:

# g++-9.3.0 -O2 -g test.cpp && perf record ./a.out < testcase.txt > /dev/null && perf report

    92.85%  a.out    a.out                [.] solve()::{lambda(auto:1, int, int)#1}::operator()<{lambda(auto:1, int, int)#1}>
     2.11%  a.out    a.out                [.] solve
     0.76%  a.out    libstdc++.so.6.0.29  [.] std::num_get<char, std::istreambuf_iterator<char, std::char_traits<char> > >::_M_extract_int<long>
     0.46%  a.out    libc-2.33.so         [.] _int_malloc
     0.40%  a.out    libc-2.33.so         [.] _int_free
     0.38%  a.out    a.out                [.] std::vector<int, std::allocator<int> >::_M_realloc_insert<int const&>
     0.38%  a.out    libc-2.33.so         [.] malloc_consolidate
     0.37%  a.out    libc-2.33.so         [.] cfree@GLIBC_2.2.5
     0.34%  a.out    libc-2.33.so         [.] __memmove_sse2_unaligned_erms
     0.32%  a.out    libc-2.33.so         [.] unlink_chunk.isra.2
     0.29%  a.out    libc-2.33.so         [.] malloc


# perf stat ./a.out < testcase.txt > /dev/null

 Performance counter stats for './a.out':

          5,079.73 msec task-clock:u              #    1.000 CPUs utilized          
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
             8,253      page-faults:u             #    0.002 M/sec                  
    14,121,518,317      cycles:u                  #    2.780 GHz                    
    12,510,832,066      stalled-cycles-frontend:u #   88.59% frontend cycles idle   
    10,556,594,313      stalled-cycles-backend:u  #   74.76% backend cycles idle    
     3,359,030,926      instructions:u            #    0.24  insn per cycle         
                                                  #    3.72  stalled cycles per insn
       546,097,415      branches:u                #  107.505 M/sec                  
        25,891,347      branch-misses:u           #    4.74% of all branches        

       5.080345274 seconds time elapsed

       5.040075000 seconds user
       0.040000000 seconds sys

So the time is now spent in the solve() function. Branches are predicted just fine, but only 0.24 instructions per cycle IPC is very bad. Such low performance is primarily caused by data cache misses. And 64-bit code is noticeably slower than the 32-bit code for both GCC 7.x and GCC 9.x, because 64-bit pointers (such as return addresses on stack and other data) have a larger footprint and suffer more from cache thrashing.

Some performance improvements are possible. Sorting nodes in the adjacency list partially reverses randomization and can make memory access pattern a bit more cache friendly (this helps with the current codeforces testcases, but is not always effective). Reworking DFS to manually enforce inlining also helps to reduce the amount of data pushed to stack. Here's my modification of LeoPro's solution: 128685795 (64-bit version, 1154 ms) and 128686428 (32-bit version, 873 ms).