We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. The Story of a Tree
  5. Discussions

The Story of a Tree

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 59 Discussions, By:

recency

Please Login in order to post a comment

  • simone_riedi27
    6 months ago+ 0 comments

    Python 3:

    def dfs(v, adj_list, parent):
        for u in adj_list[v]:
            if u != parent[v]:
                parent[u] = v
                dfs(u, adj_list, parent)
    
                
    def sum_dfs(v, p, adj_list, count, k):
        count[v] += int(p != -1) * count[p]
        out = count[v] >= k
        for u in adj_list[v]:
            if u != p:
                out += sum_dfs(u, v, adj_list, count, k)
        return out
    
                
    def storyOfATree(n, edges, k, guesses):
        adj_list = {i:set() for i in range(n)}
        for u, v in edges:
            adj_list[u-1].add(v-1)
            adj_list[v-1].add(u-1)  
        parent, count = [0]*n, [0]*n
        dfs(0, adj_list, parent)
        for u, v in guesses:
            if parent[v-1] == u-1:
                count[0] += 1
                count[v-1] -= 1
            else:
                count[u-1] += 1
        n_correct = sum_dfs(0, -1, adj_list, count, k)
        out = Fraction(n_correct, n)
        return f"{out.numerator}/{out.denominator}"
    
    -1|
    Permalink
  • r96941085
    8 months ago+ 0 comments

    Python 3: dono what's wrong with my code orz~~

    def storyOfATree(n, edges, k, guesses):
        cnn=[[] for _ in range(n+1)]
        for p,q in edges:
            cnn[p].append(q)
            cnn[q].append(p)
        win1=0
        vist=[0]*(n+1)
        cur=[1]
        while cur:
            st=cur[0]
            del cur[0]
            if not vist[st]:
                vist[st]=1
                for ed in cnn[st]:
                    if not vist[ed]:
                        win1+=[st,ed] in guesses
                        cur.append(ed)
        vist=[-1]*(n+1); vist[0]=0
        cur=[(1,win1)]
        while cur:
            st,win=cur[0]
            del cur[0]
            if vist[st]==-1:
                vist[st]=win
                for ed in cnn[st]:
                    if vist[ed]==-1:
                        cur.append((ed,win+([ed,st] in guesses)-([st,ed] in guesses)))
        wincount=sum([1 for x in vist if x>=k])
        return '{}/{}'.format(wincount//(math.gcd(wincount,n)),n//(math.gcd(wincount,n)))
    
    -1|
    Permalink
  • vonstuckrad
    1 year ago+ 0 comments

    I found this tough to implement, since a recursive dfs can easily overflow the stack for trees as large as 10^5 nodes..

    0|
    Permalink
  • Yasen
    2 years ago+ 0 comments

    For all java versions the loop in main() which iterates over "g" iterates over "q" instead.

    0|
    Permalink
  • bhuvanchandra825
    2 years ago+ 1 comment

    Don't try to fill the given function, clean the editor and start from scratch , I thought my code has problem and started debugging but the given input to the function is wrong It took me 3 hours to figure it out , to know that value of 'g' is wrong i.e guesses.size().

    Hint: If you have any doubt just think it as dfs and parent marking if you can't figure it how this is my code See only when you think you have tried hard. Another Hint: Take 1 as node draw a directed graph and try code

    int gcd(int a,int b)
    {
        if(a==0)
        {
            return a;
        }
        else if(b==0)
        {
            return a;
        }
        else {
            return gcd(b,a%b);
        }
    }
    
    void dfs(int i,int pa,vector<int> adj[],vector<int> &par,vector<bool> &vis,vector<int> guess[],int &ans)
    {
        par[i] = pa;
        vis[i] = 1;
        for(auto a:adj[i])
        {
            if(!vis[a])
            {
                for(auto b:guess[i])
                {
                    if(b==a)
                    {
                        ans++;
                        break;
                    }
                }
                dfs(a,i,adj,par,vis,guess,ans);
            }
        }
    }
    
    void s_dfs(int i,vector<int> adj[],vector<int> &par,vector<bool> &vis,vector<int> guess[],int ans,int &root_count,int k)
    {
        vis[i] = 1;
        int c;
        for(auto a:adj[i])
        {
            if(!vis[a])
            {
                c = ans;
                for(auto b:guess[i])
                {
                    if(b==a)
                    {
                        ans--;
                        break;
                    }
                }
                par[i] = a;
                par[a] = 0;
                for(auto c:guess[a])
                {
                    if(c==i)
                    {
                        ans++;
                        break;
                    }
                }
                if(ans>=k)
                {
                    root_count++;
                }
                s_dfs(a,adj,par,vis,guess,ans,root_count,k);
                ans = c;
                par[i] = 0;
                par[a] = i;
            }
        }
    }
    
    string storyOfATree(int n, vector<int> adj[], int k, vector<int> guess[],int g) {
        
        vector<bool> vis(n+1,0);
        vector<int> par(n+1,0);
    
        int ans = 0;
        int root_count = 0;
    
        dfs(1,0,adj,par,vis,guess,ans);
        if(ans>=k)
        {
            root_count++;
        }
        vector<bool> vvis(n+1,0);
        s_dfs(1,adj,par,vvis,guess,ans,root_count,k);
        
        string s="";
        int a = gcd(root_count,n);
        if(a==0)
        {
            a=1;
            n = 1;
        }
        root_count = root_count/a;
        s += to_string(root_count);
        s += '/';
        n = n/a;
        s += to_string(n);
        return s;
    }
    
    int main()
    {
        int T;
        cin >> T;
        while(T--)
        {
            int n;
            cin >> n;
            vector<int> adj[n+1];
            int x,y;
            for(int i=1;i<n;i++)
            {
                cin >> x >> y;
                adj[x].push_back(y);
                adj[y].push_back(x);
            }
            int g,k;
            cin >> g >> k;
            vector<int> guesses[n+1];
            for(int i=0;i<g;i++)
            {
                cin >> x >> y;
                guesses[x].push_back(y);
            }
            cout << storyOfATree(n, adj,k,guesses,g) << "\n";
        }
        
        return 0;
    }
    

    changing the directions while traversing dfs and changing parents. code:

    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy