Snapper_001's blog

Codenation Problem tree queries
By Snapper_001, history, 2 years ago, In English

Problem Description

You love strings a lot, so you decided to play the following game.

You have a tree T of A nodes. The tree is represented by a matrix B of dimensions (A — 1) * 2 such that there exist an edge between node B[i]|1| and B[i][2]

Each node is assigned a lowercase english character, which is represented by a string C of length A. Node is assigned character at position i of string C. You are given Q queries in the form of a matrix D of dimensions Q * 2 For each you query you will perform the following steps:

  1. You will move from node p[i][1] to node D[i][2] using the shortest possible path.

  2. Let V[1], V[2]...V[K] be the nodes visited in the corresponding order. Create a string $ such that length of S is equal to K and S[i]=c[v|i]]

  3. Store string S in your bag.

Return the number of unique strings you would create.

Problem Constraints

I <= A <= 10 ^ 5

B is a matrix of dimensions (A — 1) * 2

Feel free to share aprroaches Thanks in Advance

1<=B[i][1] , B[i][2] <= A

length(C) = A

Conly contains lowercase english alphabets

1 <= Q <= 10 ^ 5

D is a matrix of dimensions Q * 2

1<=D[i][1],D[i][2]<=A

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

Any approach is welcome. Thanks in advance

→ Reply
»
14 months ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Used string hashing.

const int M=1e9+7;

int power(int a,int b){
    int ans=1;
    while(b>0){
        if(b%2==1){
            ans*=a;
            ans%=M;
        }
        a=(a*a)%M;
        b=(b>>1);
    }
    return ans;
}

int lca(int u,int v,vector<int>&level,vector<vector<int>>&dp){
    if(level[u]<level[v]){ 
        swap(u,v);
    }
    int diff=level[u]-level[v];
    for(int i=0;i<30;i++){
        if(((1LL<<i)&diff)>0){
            u=dp[u][i];
        }
    }
    if(u==v){
        return u;
    }
    for(int i=30-1;i>=0;i--){
        if(dp[u][i]!=dp[v][i]){
            u=dp[u][i];
            v=dp[v][i];
        }
    }
    return dp[u][0];
}

void dfs(int node,int par,vector<int>&level,vector<int>&dp_rn,vector<int>&dp_nr,string &c,vector<vector<int>>&dp,vector<vector<int>>&g){
    if(node==0){
        level[0]=0;
        dp[node][0]=0;
        dp_nr[node]=c[node]-'a';
        dp_rn[node]=c[node]-'a';
    }else{
        level[node]=level[par]+1;
        dp[node][0]=par;
        dp_rn[node]=((power(26,level[node])*(c[node]-'a'))%M+dp_rn[par])%M;
        dp_nr[node]=(c[node]-'a'+(dp_nr[par]*26)%M)%M;
    }
    for(int i=1;i<30;i++){
        dp[node][i]=dp[dp[node][i-1]][i-1];
    }
    for(auto child:g[node]){
        if(child!=par){
            dfs(child,node,level,dp_rn,dp_nr,c,dp,g);
        }
    }
}

int solve(int a,vector<vector<int>>&b,string &c,vector<vector<int>>&d){
    int n=a;
    vector<vector<int>>g(n);
    for(int i=0;i<b.size();i++){
        g[b[i][0]-1].push_back(b[i][1]-1);
        g[b[i][1]-1].push_back(b[i][0]-1);
    }
    vector<int>dp_rn(n);
    vector<int>dp_nr(n);
    vector<vector<int>>dp(n,vector<int>(30,0));
    vector<int>level(n,0);
    dfs(0,-1,level,dp_rn,dp_nr,c,dp,g);
    set<int>ans;
    for(int i=0;i<d.size();i++){
        int u=d[i][0],v=d[i][1];
        u--;v--;
        int l=lca(u,v,level,dp);
        int v1=(dp_nr[u]-(dp_nr[l]*power(26,level[u]-level[l]))%M+M)%M;
        int v2=dp_rn[v]-(l==0?0:dp_rn[dp[l][0]]);
        v2=(v2*power(power(26,level[l]),M-2)%M);
        int val=(v1+(v2*power(26,level[u]-level[l]))%M)%M;
        ans.insert(val);
    }
    return ans.size();
}
→ Reply