PikMike's blog

By PikMike, history, 4 days ago, In English,

1101A - Minimum Integer

Tutorial
Solution (BledDest)

1101B - Accordion

Tutorial
Solution (Vovuh)

1101C - Division and Union

Tutorial
Solution (adedalic)

1101D - GCD Counting

Tutorial
Solution (PikMike)

1101E - Polycarp's New Job

Tutorial
Solution (PikMike)

1101F - Trucks and Cities

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1101G - (Zero XOR Subset)-less

Tutorial
Solution (PikMike)
 
 
 
 
  • Vote: I like it  
  • +22
  • Vote: I do not like it  

»
4 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Help in C

If we've found such ri then all prefix goes to one group and suffix — to another. ??

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    look at it in this way... if we have such an ri.. then that means all the segments that lie on the right side of current index have their l and r greater than ri... and all the segments before have their l and r <= current ri.. so ri can work as a boundary point where every thing on left can go to one set and everything on right go to the other.

»
4 days ago, # |
Rev. 2   Vote: I like it +42 Vote: I do not like it

I am totally not understand the solution of problem G, can anyone help me ? :(((

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your fast Editorials <3

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please explain D. GCD Counting

»
4 days ago, # |
  Vote: I like it +30 Vote: I do not like it

Your proof of the solution of problem G suggests that one can do something a little bit simpler.

Just write all the numbers in base 2 and put them as rows of a matrix (the order doesn't matter). Then the answer is just the rank of that matrix. Of course, the corner case has to be taken into account, i.e. if the xor of all numbers equals zero, then the answer is -1.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Oh, I agree! Of thought of prefix XORs for so long that I missed the thing the prefix XOR is a linear combination of the numbers in it itself.

»
4 days ago, # |
Rev. 3   Vote: I like it +48 Vote: I do not like it

I don't care if this is downvoted but Problem D editorial is not properly written.
Problems with the editorial in D.
1. " Let's for each v calculate the path of the maximum length to pass through it "
It does not say why are we calculating it and where are we using this.
2. The last paragraph seems to be the heart of algorithm and it is written in just two lines without much explanation.
3. The code uses dp to store something but the editorial doesn't mention anything about it and so for someone who is reading through the code how the hell are we supposed to know what is dp[i].
4. The code is not properly commented.

I don't know if the author write editorial for those who already know how to solve the problem. CF editorials are fast, which is great but they need a more of detailing.
Apart from this the contest and problems were great!
Lastly can anybody explain the solution for problem D?:p

  • »
    »
    4 days ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Sure, the solution must be detailed for people with low rating like me, because its an educational round.

    Thirst of all it should contained the definitions of tree. That is the difference between tree from this task and graph. What is the the simple path (probably some pictures will help me)?

    Every time I'm solving Codeforces contest dynamic or graph tasks stopped me. Please help or Ill never have progress here.

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Thirst of all it should contained the definitions of tree. That is the difference between tree from this task and graph. What is the the simple path.
      All I am saying is the editorial should be such that the main algorithm used to solve the problem should be properly conveyed to the audience(and thus more detailing of that is required) and not the things you are talking about.

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        I agree I failed at explaining the solution and I'm sorry for it.

        I genuinely tried to cover the parts that I believe to matter to the solution. I prefer to think of included code as a reference to one of the possible implementations of editorial, not the only one of the kind. The part with two pointers and such definitely takes the most number of lines in my code, but no way it's the most important. Like you don't even have to do two pointers over there, there are multiple ways to update the answer with the array of values for children.

        The editorial, though, came out to be understandable only for those who have already coded the similar things, whoops.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can say that again.

  • »
    »
    3 days ago, # ^ |
    Rev. 3   Vote: I like it +22 Vote: I do not like it

    Here is my approach to problem D (Although I did a silly mistake during contest but was able to solve after the contest)

    Firstly I rooted the tree at 1st node (you can root it at any node). I kept a map for every node which denotes the following — dp[u][gcd] = dist , where dist is maximum distance possible in a path that starts with a node that is in subtree of u and ends at node u and the gcd of the path is gcd.

    How to calculate this?

    This can be done using dfs. Initially for every node put dp[u][a[u]] = 1 if a[u] is not 1. Then do the following —

    void dfs(int u, int p) {
        for(auto v: adj[u]) {
            if(v == p) continue;
            for(auto it: dp[v]) {
                int gcd = __gcd(a[u], it.F);
                if(gcd != 1)
                    dp[u][gcd] = max(dp[u][gcd], it.S + 1);
            }
        }
    }
    

    Why do we need this?

    For each node u we have two options -

    1. Either choose two children x, y that are connected to node u such that dp[x][g1] = dist1 and dp[y][g2] = dist2 and gcd(g1, g2, a[u]) != 1, ans = max(ans, dist1 + dist2 + 1)
    2. Choose any one of the child and go to the parent and repeat the same. For one child the ans is stored in dp itself.

    This can be also incorporated in the same dfs as follows —

    void dfs(int u, int p) {
        for(auto v: adj[u]) {
            if(v == p)
    	    continue;
    	dfs(v, u)
    	if(__gcd(a[v], a[u]) != 1) {
    	    for(auto i: dp[v]) {
    		for(auto j: dp[u]) {
    		    if(__gcd(i.F, j.F) != 1) {
    		        ans = max(ans, i.S + j.S);
    		     }
    		}
    	    }
    	}
    	for(auto it: dp[v]) {
    	    int gcd = __gcd(a[u], it.F);
    	    if(gcd != 1)
    	        dp[u][gcd] = max(dp[u][gcd], it.S + 1);
    	}
        }
    }
    

    The trick is that when we are visiting i'th child, the ans upto (i — 1)'th child would already be included in the parent's dp and could be used.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Awesome, I don't get why this isn't the tutorial for problem D. It is way more understandable

    • »
      »
      »
      3 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Awesome tutorial __naruto__!
      I think there is a minor error in the code in the if condition ( if(_gcd(a[v], a[u]) != -1)_ ) shouldn't it be if(_gcd(a[v], a[u]) != 1)_ in the second code.

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Hmm, let's try this one more time but with references to the code. The code contains:

    dp[v] — the vector of the pairs (p, len) — the length of the maximum path that goes through v such that all numbers on it is divisible by p; calc(v) — dfs to calc children before the parent.

    After I calculate dp[u] for all children u of v, I take all these vectors and merge them into a single vector chd. I'll use it now to update the answer. Let's look into two kinds of paths to go thorough v:

    1. for some p chd includes only one pair such that chd[i].first = p. If a[v]%p = 0, then you can extend this path to v (update the answer with chd[i].second + 1), otherwise update the answer with chd[i].second;
    2. for some p chd includes multiple pairs such that chd[i].first = p. You want the total path to be the longest one, thus you should choose the two longest pairs from chd. Store it in mx1 (the larger of two) and mx2. If a[v]%p = 0, then update the answer with mx1 + 1 + mx2, otherwise — with mx1.

    And the final part is calculating dp[v]. Take all chd pairs and extend the possible ones to v. If some primes of a[v] were not included in there, push pairs (p, 1) for them.

»
4 days ago, # |
  Vote: I like it +30 Vote: I do not like it

Bonus for G: Prove that answer doesn't change if we permute elements of array a.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Why is this downvoted?) It isn't that obvious from the editorial and jury's solution as well.

»
4 days ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

Since PikMike says so, I'll explain the model solution for D.

What does it mean that the greatest common divisor of some set of numbers is not 1? It means that there exists some prime number p that divides the greatest common divisor. Therefore, it divides all the numbers in a set. Okay, now we can fix some prime number p, find the best path that passes only through vertices with ai divisible by p, then fix another prime, and check all the primes from 2 to 199999 this way.

What happens when we fix a prime number? Basically, the vertices of the graph are now divided into two groups: those that are forbidden to pass through (having ai not divisible by p) and those that are allowed. Let's delete all forbidden vertices from the tree (and all the edges that are incident to at least one forbidden vertex).

What will the resulting graph look like? It might become disconnected (for example, in the first sample case, if we fix p = 2, vertices 1 and 3 are disconnected), but it's still acyclic because removing edges or vertices from a graph won't create a new cycle. So, each connected component of the graph is a tree. Now we have to find the best path in each connected component.

Okay, how to determine the "best" path? If the number of vertices on a path is x, and the path is simple, then the number of edges belonging to this path is x - 1. And since each component is a tree, then we are interested in finding the diameter of the tree, which can be done in O(|V|): pick some vertex from the tree (let's denote it as v0), run DFS or BFS from it, find the vertex having the greatest distance from v0 (let it be v1; if there are muliple such vertices, pick any of them), run DFS or BFS from it, and find some vertex having greatest vertex from v1 (let it be v2). The path between v1 and v2 is the diameter.

Why does it work fast enough? Each number exceeding A can have no more then prime divisors, so the sum of sizes of the graphs we are finding the diameters in is bounded as .

Okay, how to implement it? When we pick some prime p, instead of deleting forbidden vertices and edges (which leads us to complexity of O(nA) or even greater), let's create a new graph: renumerate all allowed vertices so that their numbers become 1, 2, ..., k, and apply the aforementioned solution to this graph. That is the easiest way to make it without using some auxiliary sets or other data structures.

upd: Well, in fact, model solution is because I was too lazy to write fast factorization algorithms. But it's worth mentioning that if you want to achieve complexity of , there's no need to write Eratosthenes sieve: finding all divisors of all numbers from 1 to A in can be done using two nested for loops, the outer one iterating on the divisor, and the inner one iterating on the numbers divisible by that divisor.

»
4 days ago, # |
  Vote: I like it -15 Vote: I do not like it

In C part for the test case 1 4 1 2 2 4 4 8 5 10. the output should be 1 1 1 2 but according to the editorial it's giving -1

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    [4, 8] and [5, 10] intersect.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks i misinterpreted the question as for segment[ li, ri] i didn't thought it meant range li to ri. BTW what's a good approach to solve the question if instead of segments, sets with discrete value is given. For ex. {1,2,3},{2,3,4},{7,8,9} (ans-1 1 2) .Should i use set_intersection and iterate over all sets?

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Build an undirected graph with two types of vertices: vertices representing numbers, and vertices representing sets. Connect all "set"-vertices with corresponding "number"-vertices. Now we have to color this graph into two colors so vertices in the same component share the same color.

»
3 days ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I get nothing from task G tutorial, could anyone explain the solution?

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain why opt[l][r][k] <= opt[l][r+1][k] in problem F..?? I am not able to visualize this.

»
3 days ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

I have a slightly different solution for F. We still calculate dp[l][r][k], and the recurrence is still . However, we notice that dp[l][j][k - 1] increases as you increase j, and a[r] - a[j] decreases as you increase j. Thus, the min value of will occur when they are as close to each other as possible, i.e. when |dp[l][j][k - 1] - (a[r] - a[j])| is minimized, and this quantity is unimodal so we can binary search for it. For memory optimization, we simply notice that we don't need to store all the queries, and can process them online, giving us O(n3) space rather than O(n3 + q), which barely fits into the memory. The DP calculation takes time, which also barely fits into the time limit.

48306162

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me in finding mistake in D? I am not able to find why it is giving WA. Submission

»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Choose your i/o functions wisely.

Actually I think a problem shouldn't be annoyed with slow i/o.But you guys should know scanf/printf is faster than cin/cout.When the input is larger than 5MB you should use scanf/printf without hestitation.

(Also the only way to make this simple problem E harder is to hack some slow i/o's...Maybe?)

»
3 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem D, I have used the concept that-For any vertex 'v' it can either be a part of the longest path or not. Then i calculated the longest path in its sub-tree and updated the max value, and then passed the value of the longest path obtained from its children to its parent. But this approach is giving wrong answer on test 5. Here is my code, why isn't this approach working. https://codeforces.com/contest/1101/submission/48279577

  • »
    »
    3 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Consider this test case :

    3
    6 2 6
    1 2
    1 3
    

    The answer should be 3 but your code outputs 2.

    The problem is with how you are calculating answer. You are returning maxx+1 and so are never considering the case when the largest path can be through one vertex conncting two nodes of the children when maxx>0. Also while calculating the ans variable you are not considering the fact that smaxx and maxx can be having their gcd = 1(eg smaxx = 3 because of path having gcd = 2 and maxx = 3 because of path having gcd = 3 and when you say answer = 3+3=6 you are considering a path having gcd(2,3) = 1). There can be more but I think these are the major ones.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://codeforces.com/contest/1101/submission/48316745 well, i am considering the case when the largest path can be through the vertex i am currently on ans = max(ans,maxx+smax+1). In the last solution i missed to give = in len>=max condition. Here maxx is the longest path in the subtree of the current vertex and smaxx is second longest. thats why maxx+smaxx+1 gives the longest path through the current vertex. Regarding your second argument that gcd(smaxx,maxx)=1. why would i be taking gcd of length of the paths.

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't mean length of paths, I meant the gcd of all ai s in the path

        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got the problem with my code. its failing on test 27 which is. 4 3 6 2 2 1 2 2 3 3 4 outputting 2 instead of 3. thanks anyways!!

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And it is still giving wrong answer for the test case I provided above.

»
3 days ago, # |
  Vote: I like it +2 Vote: I do not like it

I have another idea about D but I got WA. Could anybody help me?

I tried to deal with it by DP in trees. Denote dp[i] as a set where stored some pairs (g, d). A pair (g, d) in dp[i] means a path form v to vertex i that the gcd of vertices in the path is g and its length is d, where v is one of the grandsons of vertex i. It's evidently I needn't store the pairs (g, d) where g = 1 and also I can ignore the vertex i where a[i] = 1. And if there are two pairs which have the same g, I can ignore the one with the lower d.

Of course a pair (a[i], 1) is in dp[i] if a[i] > 1. Consider all children of vertex i, assuming that now I'm consider v. Get all pairs in dp[v], assuming that now I get (g0, d0). Insert pair (gcd(g0, a[i]), d0 + 1) to dp[i] and maintain the optimal pairs if gcd(g0, a[i]) > 1, which means vertex i links into the path. However, the answer can be the path from one of the grandsons of vertex i to another. So before the insertion, I consider all pairs in dp[i] to get the potential answer. dp[i] now stores some pairs stand for the path from vertex i to one of the grandsons of vertex u, where vertex u is one of the children which is already considered of vertex i. Assuming that I'm considering pair (g1, d1) in dp[i], ans = max(ans, d0 + d1) if gcd(g0, g1) > 1.

I don't know what's wrong with my approach or my code because of my poor ability. Here's my Submission 48313349. I'd appreciate it if someone help me.

Sorry for my poor English.

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    It seems, you return from dfs when au = 1. I believe, that best answer might be in a subtree of such a vertex, but you won't reach it.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes. What a stupid mistake I made! Thanks a lot! :)

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I still got WA. :(

      My answer is greater on test 6. Could you help me again? Thanks. 48320981

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Try this test

        4
        4 4 2 4
        1 2
        2 3
        2 4
        
        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you very much! I knew how to improve my approach. :)

    • »
      »
      »
      35 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why is my brute force solution giving wrong answer on test 4 code

      i am considering all pairs of vertices which could give the correct answer and by using bfs i calculate dist and gcd values for all pairs of vertices with source as s. But this gives wrong answer on test 4 . Can you help me??

      • »
        »
        »
        »
        35 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The idea of brute is ok, your bfs has a bug in it.

        • »
          »
          »
          »
          »
          34 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Gotcha sorry i forgot to push children to queue

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Hi, Your code is a bit difficult to read, but I've found a testcase, for which you code outputs Wrong Answer. Since Testcase 6 is big, so it would be harder to debug, so try this:

    4
    2 6 3 2
    1 2
    2 3
    2 4
    
    
    

    Correct Answer is 3 and your code is outputting 4.

    Hope this helps

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know what mistake I've made now. As I insert pairs into dp[i], I may get the two paths from the same child. So I can insert them to another set so that I can't reach them when considering the child. And in the end I insert them into dp[i]. I finally got AC! Thank PikMike and atom0410! :)

»
3 days ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

I just found out my solution for problem D was incorrect . But yet I got AC even after the system test . It happened because of weak test cases .

Test Case # X :
4
3 6 2 2
1 2
2 3
3 4

My Submission :
48253431

The correct answer should be 3 , but my solution is giving 2 .
Can you guys rejudge problem D

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Aha! I love problem F.

I solved this problem by randomization and binary search. The code is easy to read. 48318449

Let us analyze this problem, we know every truck must have the max gas-tanks. For a truck, the more oil, the better.

We randomly choose a truck to calculate ( use binary search ), It can be considered that in general, half of the trucks do not exceed the maximum fuel consumption. In other words, we only use logm operations( binary search) at most.

»
3 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey PikMike , I am not able to understand that why solution for E getting TLE thought its complexity is O(N), but it is accepted when i used ios::sync_with_stdio(false); cin.tie(0); N <= 500000 Solution ID : https://codeforces.com/contest/1101/submission/48324180 Solution ID (without ios::...) : https://codeforces.com/contest/1101/submission/48324102

And the time limit for Question is 3sec.

Can you help with this, Thanks in advance:)

»
3 days ago, # |
  Vote: I like it +6 Vote: I do not like it

for problem D fix a prime p and find longest path with vertices divisible by p! Consider the vertices divisible by p, there are some disjoint maximal subtree with all vertices divisible by p obviously the longest path is diameter of one of these subtrees. so we will find for each vertex v and prime p as prime factor of v , the diameter of the subtree contains v , it can be done with dp on tree! we have nlogMAXN pair(v,p) and each dfs goes to some of them so in total we visit nlogMAXN state, also to avoid going to each subtree many time we should mark state (v,p) if we use a set the time will be nlog^2(MAXN) or if we use an array of sets reduce it to n*logMAXN*loglogMAXN or if we use hashing it is nlogMAXN! :)

My submission

  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro, i solved D using recursion, at each node i m storing the maxdepth for each factor in its subtree, so if a parent node have three child all three child would have been processed before i come to process the parent node and again i will store the same set of variables for parent node and WILL ALSO CHECK(means consider) THE PATHS ACROSS THE CHILDS,

    this approach gives the wrong answer->https://codeforces.com/contest/1101/submission/48359404

    on 8th test case i have considered some big path which i should not have done. please help in this, code is quite clean.

»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody explain me how to check ri < min lj quickly in problem C? UPD. okay, I've tried to read code again and I think I understood.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Help T^T I still don't understand the first example provided in D. Shouldn't the output be 3 instead of 1, since the first and the third vertex has gcd greater than one with distance three? Can someone please kindly explain to me...

»
2 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Can anyone Explain the approach of problem G?

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
44 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

Cannot understand G :(

»
24 hours ago, # |
  Vote: I like it 0 Vote: I do not like it
void try_gauss(int v){
	for(int i = LOGN - 1; i >= 0; i--)
		if (base[i] != -1 && (v & (1 << i)))
			v ^= base[i];
	if (v == 0)
		return;
	for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){
		base[i] = v;
		return;
	}
}

Could someone please explain (or point to a tutorial/explanation) why this method indeed gives us the basis vectors ? Intuitively it looks like it's doing Gauss elimination but I am having a difficult time understanding how.

  • »
    »
    22 hours ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    base[i] saves some bit vector where the first 1 is in position i (by first position, I mean the largest position). Now, when we want to add some bit vector v, we try to see if we can consturct v using the unfinished basis we currently have (that is the first loop). Why the loop works? Because, that loop tries to eliminate every bit individually (based on the property from above). If it succeeds, then v will have zero value. The second part. Well, if v is not zero, then that means that our basis doesn't have a value for base[j], where j is the largest index, such that v[j] == 1. And we will just add it to our unfinished basis.

    Here is the code I use for F2 space Gauss. It is shorter and maybe more clear.

    void gauss(int mask) {
      for(int i = 0; i < n; ++i) {
        if(!(mask & (1 << i))) continue;
        if(!basis[i]) {
          basis[i] = mask;
          ++sz;
          break;
        }
        mask ^= basis[i];
      }
    }
    
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone debug the code of d given bellow?why does it give one less than actual ans?or,give me any hint

  • »
    »
    20 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    include <bits/stdc++.h>

    define LL long long

    define int64_t int

    using namespace std;

    define ff first

    define ss second

    define mp make_pair

    define pb push_back

    define ub upper_bound

    define lb lower_bound

    define inff 1e9+5

    define M %(998244353)

    //priority_queue<int, std::vector, std::greater > my_min_heap;

    define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    //#define int64_t int

    define lop(ii,n) for(int64_t ii = 1; ii <= n; ++ ii)

    define loop(ii,n) for(int64_t ii = 0; ii < n; ++ ii)

    define aloop(ii,n) for(int64_t ii = n-1; ii >=0; ii--)

    define alop(ii,n) for(int64_t ii = n; ii >0; ii--)

    define fox vox

    string s2; map<int64_t,int64_t>mp1; int64_t vr[500006]={0}; vectorvn[200005+1];

    int64_t arr[200005+1]={0},an=0; vector<pair<int64_t,int64_t> >pr; int64_t dfs(int64_t s,int64_t prm) { vr[s]=1; int64_t temp=0,tm1=0,tm2=0; loop(i,vn[s].size())if(vr[vn[s][i]]==0&&arr[vn[s][i]]%prm==0) {

    int64_t t2=dfs(vn[s][i],prm);
        if(temp==0)
            tm1=max(tm1,t2);
        else
        {
            if(tm1<t2){tm2=tm1;tm1=t2;}
            else tm2=t2;
        }
        temp=1;
    }
    an=max(an,tm1+tm2+1);
    return tm1+1;

    } int64_t prr[200009]={0}; int main() { FastIO int64_t r=0,ans=0,n=1,fu=0; cin>>n;

    //set<int64_t>st;
    //int64_t prr[n+1];
    memset(prr,0,sizeof (prr));
    lop(i,n){
    cin>>arr[i];
    r=max(r,arr[i]);
    fu=arr[i];
    //c1=0;
    for(int64_t j=2;j*j<=arr[i];j++)
        if(arr[i]%j==0)
    {
        //if(c1<j)pr.pb(j),c1=j;
        prr[j]++;
    
        //if(st.find(j)==st.end())
        //st.insert(j),pr.pb(j);
        while(arr[i]%j==0)arr[i]/=j;
    }
    if(arr[i]>1)prr[arr[i]]++;//&&st.find(arr[i])==st.end())pr.pb(arr[i]),st.insert(arr[i]);
    arr[i]=fu;
    }
    for(int64_t i=2;i<=r;i++)if(prr[i]>0)pr.pb(mp(prr[i],i));
    sort(pr.rbegin(),pr.rend());
    loop(i,n-1)
    {
        int64_t u,v;
        cin>>u>>v;
        vn[u].pb(v);
        vn[v].pb(u);
    }
    /*if(n==200000)
    {
        loop(i,pr.size())if(pr[pr.size()-i-1].ff>6)cout<<pr[pr.size()-1-i].ff<<" "<<pr[pr.size()-1-i].ss<<endl;
    }*/
    for(int64_t i=0;i<pr.size()&&pr[i].ff>an;i++)
    {
        int64_t nm=pr[i].ss;
        lop(k,n){if(vr[k]==0&&arr[k]%nm==0){int64_t yy=dfs(k,nm);pr[i].ff-=yy;}
        if(pr[i].ff<=an)break;
        }
    
        memset(vr,0,sizeof (vr));
    }
    cout<<an;

    }

»
14 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

What does even and odd number of pr[x] means in G? Can someone explain 2nd para in more approachable way?