can you share the code for 1st problem ?

Q2: Just observe that there will be a path from root to the node having value 0, outside this path all the other nodes will have their mex=0. Now for this particular path we can maintain an array starting from the node having value 0 to the root and marking all the values in that particular subtree.

.

how to do 1st and what is harmonic series

For Q2 use an Euler's tour on tree and store the flattened tree in array, then you can query on subarray for every node to calculate MEX of each node, you can use segment tree for calculating MEX for each query.

Total complexity: $$$O(nlogn)$$$

Someone asked me the second problem as a doubt after their round had ended.
The first solution I came up with was $$$N.log^2N$$$ using DSU on trees.

I think the tree question can be done in nlogn using set. Where set will repersent all the values that are not present in the whole substree and the merge the left and right subtree set and ans for i will be *st.begin()

For Ques 3 you can use Segment Tree. It is a very general ST problem (refer this)

Finding subsegments with the maximal sum -> scroll down to this topic in above link.

It is almost same as given in the above link, the only difference is that you have to create 2 segment trees,

first for(-a[0],a[1],-a[2]...a[n]) and second for (a[0],-a[1],a[2],-a[3].....-a[n]).

Now depending upon the query type you can find the maximal subarray sum accordingly.

Also note that in the update query you will have to update both of your segment trees.

This is my proposed solution for Q2

Let loc[x] be the location of node with value x , Let LCA(x,y) be the lowest common ancestor of node x and y ,

Then LCA(loc[1],loc[0]) and its ancestors will have mex >=2 , LCA(LCA(loc[0],loc[1]),loc[2]) and its ancestors will have mex >=3 and so on...

Can anyone confirm if this will work ?

Found video editorials for these questions.

One can try GSS3 on spoj. It's similar to 2nd problem.

How will we do the question 2 if the nodes don't have distinct values and also the values ranges from 0 to 1e9?

Question 2

Observation 1: If there is No zero ans will be 0 for all

Observation 2: The nodes which occur in between from root to node which has zero value they will have MEX > 0

Approach: Find node with 0 value (say NODE) and do dfs mark all values which are in the subtree of that node,

use a variable (say mex = 0) that will store ans for this node. while mex is marked true as visited increase it and find first missing positive. now move NODE to parent[NODE]

Do this while NODE != -1

class Solution {
public:
    vector<vector<int>> adj;
    vector<int> vis;
    void dfs(int curr, vector<int>&nums){
        vis[nums[curr]] = 1;
        for(int v : adj[curr]){
            if(!vis[nums[v]])
                dfs(v, nums);
        }
    }
    
    vector<int> MexSubTree(vector<int>& parent, vector<int>& nums) {
        int n = parent.size();
        int idx = -1;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0){
                idx = i;
                break;
            }
        }
        vector<int> ans(n, 0);
        if(idx == -1)return ans;
        adj.resize(n);
        vis.resize(n+2, false);
        int MEX = 0;
        for(int i = 1 ; i < n ; i++){
            adj[parent[i]].push_back(i);
        }
        while(idx != -1){
            dfs(idx, nums);
            while(vis[MEX])
                MEX++;
            ans[idx] = MEX;
            idx = parent[idx];
        }
        return ans;
    }   
};

Easy to understand and simple solutions,

Alternating queries: https://ideone.com/LFGNGG
Find mex in tree: https://ideone.com/tfUIEn

Hats off to the authors, who created these. Truly mind-blowing problems.