vector<VII> adj(2e5);
map<int, VII> col;
VII sub(2e5, 0);
VII ind(2e5, 0);
VII v(2e5);
int t = 1;
int dfs(int u,int p)
{
    for(auto it:adj[u])
    if(it!=p)
        sub[u] += dfs(it, u);
    
 
    ind[u] = t++;
    col[v[u]].pb(ind[u]);
    sub[u]++;
    return sub[u];
}
int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n;++i)
        cin >> v[i];
 
    for (int i = 0; i < n - 1;++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
 
    dfs(1, -1);
    for (int i = 1; i <= n;++i)
    {
        int l = ind[i] - sub[i] + 1;
        int r = ind[i];
        int ans = 0;
        for(auto c:col)
        {
            auto lll = lower_bound(all(c.second), l);
            auto rr = upper_bound(all(c.second), r);
            if(rr-lll>=1)
                ans++;
        }
        cout << ans << ' ';
    }
    return 0;
}

const int MOD=(1e9+7);
class Solution {
    vector<int> gp,pf;
    int g,p;
    int n;
public:
    long long solve(int i,int tg,int tp)
    {
        if(tg<0)return 0;
        
        if(i>=n && tp>=p)return 1;
        if(i>=n)return 0;
        
        return (solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;
    }
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        gp=group;
        pf=profit;
        g=G;
        p=P;
        n=group.size();
        
        long long ans=solve(0,G,0);
        return ans%MOD;
    }
};

const int MOD=(1e9+7);
class Solution {
    vector<int> gp,pf;
    int g,p;
    int n;
    int dp[101][101][1000];
public:
    long long solve(int i,int tg,int tp)
    {
        if(tg<0)return 0;
        
        if(i>=n && tp>=p)return 1;
        if(i>=n)return 0;
        if(dp[i][tg][tp]!=-1)return dp[i][tg][tp];
        return dp[i][tg][tp]=(solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;
    }
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        gp=group;
        pf=profit;
        g=G;
        p=P;
        n=group.size();
        memset(dp,-1,sizeof(dp));
        long long ans=solve(0,G,0);
        return ans%MOD;
    }
};

Diagnostics detected issues [cpp.g++17-drmemory]: Dr,2020-03-13.M Dr. Memory version 1.11.0 Dr,2020-03-13.M Running "program.exe"

This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information. C:/Programs/mingw-w64-7/lib/gcc/i686-w64-mingw32/7.3.0/include/c++/debug/vector:417: Error: attempt to subscript container with out-of-bounds index 2, but container only holds 2 elements.

Objects involved in the operation: sequence "this" @ 0x00300060 { type = std::__debug::vector<int, std::allocator >; } Dr,2020-03-13.M Dr,2020-03-13.M NO ERRORS FOUND: Dr,2020-03-13.M 0 unique, 0 total unaddressable access(es) Dr,2020-03-13.M 0 unique, 0 total uninitialized access(es) Dr,2020-03-13.M 0 unique, 0 total invalid heap argument(s) Dr,2020-03-13.M 0 unique, 0 total GDI usage error(s) Dr,2020-03-13.M 0 unique, 0 total handle leak(s) Dr,2020-03-13.M 0 unique, 0 total warning(s) Dr,2020-03-13.M 0 unique, 0 total, 0 byte(s) of leak(s) Dr,2020-03-13.M 0 unique, 0 total, 0 byte(s) of possible leak(s) Dr,2020-03-13.M ERRORS IGNORED: Dr,2020-03-13.M 2 potential error(s) (suspected false positives) Dr,2020-03-13.M (details: K:\invoker-prod\work\codeforces6\1843d7698c4806cf9d85184a84ec46ea\check-7d3733f84f4a8e2ab0065b77fcdbaa35\run\DrMemory-program.exe.4504.000\potential_errors.txt) Dr,2020-03-13.M 18 unique, 36 total, 168416 byte(s) of still-reachable allocation(s) Dr,2020-03-13.M (re-run with "-show_reachable" for details) Dr,2020-03-13.M Details: K:\invoker-prod\work\codeforces6\1843d7698c4806cf9d85184a84ec46ea\check-7d3733f84f4a8e2ab0065b77fcdbaa35\run\DrMemory-program.exe.4504.000\results.txt Dr,2020-03-13.M WARNING: application exited with abnormal code 0x3

I was able to think of it as a pattern but I'm not sure if its right or wrong.

0=>0

1=>1 2

2=>3 4 5

3=>6 7 8 9

4=>10 11 12 13 14

and so on

I was trying to preprocess it but ended up with TLE anybody could tell me how to approach this problem?

I was thinking it as a way to represent overlappings with graphs maybe?

Couldn't think anything more than that it would be great if you guys could tell me how to approach this.

I tried to build a recurrence relation which is not memoizable easily so I think My recursive function was wrong. It gave me right answers for few cases rest were TLE. Every time I am able to think only Memory heavy and time heavy logic. A generic way to think for such problems would be great.

My recursive solution:

void vis(string t1,string t2,int i)
{
    if(t1==t2){
        ans=max(ans,2*t1.size());
    }
    if(i>=s.size())return;

    vis(t1+s[i],t2,i+1);
    vis(t1,t2+s[i],i+1);
    vis(t1,t2,i+1);
}

Initial idea was to do dfs for each query (i know it ends up in TLE) but for basic cases it worked. I passed frequency array across each step of recursive dfs(very memory intensive).

I thought of like pre processing i.e a table to say most freq character from node x to node y. But the constraints had 1<=n<=10^6 I gave up the idea of storing n^2.

What could be the best way to handle these sorts of problems.