Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Valid Paths CodeChef Solution

Problem -Valid Paths CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Valid Paths CodeChef Solution in C++17

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 1e9 + 7;
int tc, cs = 1;

int n;
vector<int> adj[N];
int sz[N], tot;
bool dead[N];
ll ans, pw[N], dist;

ll bigmod(ll a, ll n, ll M) {
  ll res = 1LL;
  while (n) {
    if (n & 1) res = (res * a) % M;
    a = (a * a) % M;
    n >>= 1;
  }
  return res % M;
}

void dfs1(int u, int p) {
  sz[u] = 1;
  tot++;
  for (auto v: adj[u]) {
    if (v == p || dead[v]) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
}
 
int dfs2(int u, int p) {
  for (auto v: adj[u]) {
    if (v != p && !dead[v] && sz[v] > tot/2) {
      return dfs2(v, u);
    }
  }
  return u;
}

void dfs3(int u, int p, int lev, int add) {
  dist = (dist + add*pw[lev]) % mod;
  for (auto v: adj[u]) {
    if (v == p || dead[v]) continue;
    dfs3(v, u, lev + 1, add);
  }
}

ll dfs4(int u, int p, int dep) {
  ll ret = (pw[dep - 1]*dist) % mod;
  for (auto v: adj[u]) {
    if (v == p || dead[v]) continue;
    ret = (ret + dfs4(v, u, dep + 1)) % mod;
  }
  return ret;
}

void decompose(int root, int dep) {
  tot = 0;
  dfs1(root, root);
  int u = dfs2(root, root);
  dist = 0;
  dfs3(u, u, 0, 1);
  ll add = ((dist - 1)*bigmod(2LL, mod - 2, mod)) % mod;
  for (auto v: adj[u]) {
    if (dead[v]) continue;
    dfs3(v, u, 1, -1);
    add = (add + dfs4(v, u, 1)) % mod;
    dfs3(v, u, 1, +1);
  }
  ans = (ans + add) % mod;
  dead[u] = 1;
  for (auto v: adj[u]) {
    if (dead[v]) continue;
    decompose(v, dep + 1);
  }
}

void test_cases() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    adj[i].clear();
    dead[i] = 0;
    sz[i] = 0;
  }
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  ans = 0;
  decompose(1, 0);
  ans = (ans * bigmod(2, mod - 2, mod)) % mod;
  ans = (ans + n) % mod;
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  pw[0] = 1;
  for (int i = 1; i <= N-10; ++i) pw[i] = (pw[i - 1] * 2LL) % mod;
  cin >> tc;
  while (tc--) {
    test_cases();
  }
}

Valid Paths CodeChef Solution in C++14

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
inline ll read()
{
	ll sum=0,l=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')l=-1;c=getchar();}
	while(isdigit(c)){sum=sum*10+c-'0';c=getchar();}
	return sum*l;
}
vector<ll> a[100100];
ll ans[100100],ans2[100100],mod=1000000007;
void dfs(int x,int fa)
{
	ans[x]=0;
	ans2[x]=0;
	if(a[x][0]==1&&x!=1)
	{
		ans[x]=1;
		return;
	}
	ll b=0,c=0;
	for(int i=1;i<=a[x][0];i++)
	{
		if(fa==a[x][i])
		{
			continue;
		}
		dfs(a[x][i],x);
		ans2[x]+=ans[a[x][i]]*b;
		ans2[x]%=mod;
		b+=ans[a[x][i]];
		b%=mod;
		c+=ans2[a[x][i]];
		c%=mod;
	}
	ans2[x]=(ans2[x]*2%mod+c)%mod;
	ans[x]=(2*b+1)%mod;
	return;
}
int main()
{
	ll b,c,d,e,f,g,h,i,j;
	cin>>b;
	while(b)
	{
		b--;
		c=read();
		for(i=1;i<=c;i++)
		{
			a[i].clear();
			a[i].push_back(0);
		}
		for(i=1;i<=c-1;i++)
		{
			d=read();
			e=read();
			a[d].push_back(e);
			a[d][0]++;
			a[e].push_back(d);
			a[e][0]++;
		}
		dfs(1,-1);
		cout<<(ans[1]+ans2[1])%mod<<"\n";
	}
	return 0;
}

Valid Paths CodeChef Solution in PYTH 3

# cook your dish here
import sys
sys.setrecursionlimit(10**9)
try:
    t = int(input())

# {1 : [2], 2 : [1]}

    def dfs(graph, node, ans, v, anc):
        v[node] = 1
        ans[0] += 1 # if u = v = node
    
        for child in graph[node]:
            if(child == anc):
                continue
            dfs(graph, child, ans, v, node)
            
            ans[0] += int((v[node] * v[child]) % (10**9 + 7))
            v[node] += int((2 * v[child]) % (10**9 + 7))
            v[node] %= (10**9 + 7)
            ans[0] %= (10**9 + 7)
            v[node] = int(v[node])
            ans[0] = int(ans[0])

        


    while(t > 0):
        n = int(input())
        if(n == 1):
            print(1)
            t -= 1
            continue
    
        graph = dict()
    
        for ind in range(n-1):
            (u, v) = tuple(map(int, input().split()))
            if(u not in graph):
                graph[u] = [v]
            else:
                graph[u].append(v)
            if(v not in graph):
                graph[v] = [u]
            else:
                graph[v].append(u)
            
        ans = [0]
        v1 = dict()
    
        dfs(graph, 1, ans, v1, 1)
    
        print(int(ans[0]));
    
        t -= 1
        
except EOFError as e:
    print (e)

Valid Paths CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Tree
{
    int vertices;
    ArrayList<ArrayList<Integer>> adjL;
    Tree(int vertices)
    {
        this.vertices=vertices;
        adjL=new ArrayList<>();
        for(int i=0;i<vertices;i++)
            adjL.add(i,new ArrayList<>());
    }
    void addEdge(int u,int v)
    {
        adjL.get(u).add(v);
        adjL.get(v).add(u);
    }
}
class Codechef
{
    static int mod=1000000007;
    int sum=0;
     int vPaths(Tree tr)
    {
        int stPaths=dfs(0,tr,new boolean[tr.vertices]);
        return (int)(((long)stPaths+sum)%mod);
    }
    int dfs(int u,Tree tr,boolean[] visited)
    {
        visited[u]=true;
        int crossSum=0;
        int stPaths=0;
        for(Integer v:tr.adjL.get(u))
        {
            if(!visited[v])
            {
                int temp=dfs(v,tr,visited);
                crossSum=(int)((crossSum+((stPaths*(long)temp)%mod))%mod);
                stPaths=(int)((stPaths+(long)temp)%mod);
            }
        }
        crossSum=(int)(((long)crossSum*2)%mod);
        sum=(int)(((long)crossSum+sum)%mod);
        stPaths=(int)(((long)stPaths*2)%mod);
        return (int)((1+(long)stPaths)%mod);
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        OutputStream out = new BufferedOutputStream ( System.out );
        int T=Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            int n=Integer.parseInt(br.readLine().trim());
            Tree tr=new Tree(n);
            for(int i=0;i<n-1;i++) {
                String[] edge = br.readLine().trim().split(" ");
                int u = Integer.parseInt(edge[0]);
                int v = Integer.parseInt(edge[1]);
                tr.addEdge(u - 1, v - 1);
            }
            out.write((new Codechef().vPaths(tr)+"\n").getBytes());
        }
        out.flush();
	}
}

Valid Paths CodeChef Solution in PYPY 3

import os,sys
from io import BytesIO,IOBase

def main():
    mod = 10**9+7
    for _ in range(int(input())):
        n = int(input())
        path = [[] for _ in range(n)]
        for _ in range(n-1):
            u1,v1 = map(lambda xx:int(xx)-1,input().split())
            path[u1].append(v1)
            path[v1].append(u1)
        st,poi,visi = [0],[0]*n,[1]+[0]*(n-1)
        dp,ans = [1]*n,[1]*n
        while len(st):
            x,y = st[-1],path[st[-1]]
            if poi[x] != len(y) and visi[y[poi[x]]]:
                poi[x] += 1
            if poi[x] == len(y):
                st.pop()
                if len(st):
                    ans[st[-1]] = (ans[st[-1]]+dp[st[-1]]*dp[x])%mod
                    dp[st[-1]] = (dp[st[-1]]+(dp[x]*2))%mod
            else:
                st.append(y[poi[x]])
                visi[st[-1]] = 1
                poi[x] += 1
        su = 0
        for i in ans:
            su = (su+i)%mod
        print(su)

# Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self,file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0,2),self.buffer.write(b),self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
            self.newlines = b.count(b"\n")+(not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0,2),self.buffer.write(b),self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd,self.buffer.getvalue())
            self.buffer.truncate(0),self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self,file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s:self.buffer.write(s.encode("ascii"))
        self.read = lambda:self.buffer.read().decode("ascii")
        self.readline = lambda:self.buffer.readline().decode("ascii")
sys.stdin,sys.stdout = IOWrapper(sys.stdin),IOWrapper(sys.stdout)
input = lambda:sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
    main()

Valid Paths CodeChef Solution in PYTH

import sys
sys.setrecursionlimit(10**6)

def valid_path(graph, par, ext, prev):
    children = graph[par]
    values = []
    sum1 = sum2 = 0
    mod = 1000000007
    for child in children:
        if child != prev:
            if len(graph[child]) > 1:
                val = valid_path(graph, child, ext, par)
            else:
                val = 1
            sum1 += val
            val %= mod
            sum2 += (val*val)%mod
    ext[0] += (((sum1%mod) * (sum1%mod))%mod) - sum2
    ext[0] %= mod
    sum1 = (2*sum1) + 1
    return sum1 % mod

t = int(raw_input())
for p in range(t):
    n = int(raw_input())

    if n == 1:
        print '1'
    else:
        graph = {}

        for q in range(n-1):
            [u, v]  = map(int, raw_input().split(" "))
            if graph.has_key(u):
                graph[u] += [v]
            else:
                graph[u] = [v]

            if graph.has_key(v):
                graph[v] += [u]
            else:
                graph[v] = [u]

        ext = [0]
        mod = 1000000007

        ans = valid_path(graph, 1, ext, -1)
        ext[0] %= mod
        ans %= mod
        ans += ext[0]
        ans %= mod
        print ans

Valid Paths CodeChef Solution in C#

using System;
using System.Collections.Generic;

namespace CodeChef21._5 {
    // Prepared as a solution to Valid Paths
    // David Sturge (David_S)  11 May 2021

    class Node : IComparable
    // Node of tree
    {
        const int c_mod = 1000000007;

        public int SubDown;   // Total of subtree down from here,
                               // able to be used in combination with higher nodes
        public int SubBelow;  // Total of subtree here and below, 
                               // not able to be used in combination with higher nodes
        public int Level = 0;  // level in tree
        public List<Node> Links;  // initially parents and children, later just children
        public Node Parent = null;

        public Node()
        {
            SubDown = 1;
            SubBelow = 0;
            Links = new List<Node>();
        }

        public void EvaluateSubTotals()
        // Evaluate subtree totals at this node.
        // The total of possibilities for SubBelow (= total of subtree here and below, 
        // not able to be used in combination with higher nodes) consists of the total of
        //   the SubBelow of each child, and
        //   twice the product of the SubDown of each pair of children.
        // The total of possibilities for SubDown (= total of subtree down from here,
        // able to be used in combination with higher nodes) consists of the total of
        //   twice the SubDown of each child, and
        //   1 for this node alone.
        {
            int child_count = Links.Count;
            if (child_count > 0) {
                long exprd = 0;
                long exprb1 = 0;
                long exprb2 = 0;

                for (int i = 0; i < child_count; ++i) {
                    exprb1 += Links[i].SubBelow;
                    exprd += Links[i].SubDown;
                }

                // There may be so many children that an N^2 algorithm takes too long.
                int ilo = 0;
                if (child_count > 100) {
                    // How many of each number of subdown are there?
                    Links.Sort();
                    int c_max_combos = (int)Math.Sqrt(child_count);
                    Tuple<int, int>[] combos = new Tuple<int, int>[c_max_combos];
                    int num_combos = 0;

                    int ista = 0;
                    int dbef = 0;
                    for (ilo = 0; ilo < child_count; ++ilo) {
                        int d = Links[ilo].SubDown;
                        if (d != dbef) {
                            if (dbef != 0) {
                                combos[num_combos++] = new Tuple<int, int>(dbef, ilo - ista);
                            }
                            if (num_combos >= c_max_combos)
                                break;
                            dbef = d;
                            ista = ilo;
                        }
                    }
                    if (num_combos < c_max_combos) {
                        combos[num_combos++] = new Tuple<int, int>(dbef, ilo - ista);
                    }

                    for (int i = 0; i < num_combos; ++i) {
                        // Products of pairs of combinations the same
                        Tuple<int, int> tup = combos[i];
                        long di = tup.Item1;
                        int ni = tup.Item2;
                        exprb2 += ((((di * di) % c_mod) * ni * (ni - 1)) / 2) % c_mod;
                        // Products of pairs of different combinations
                        for (int j = 0; j < i; ++j) {
                            tup = combos[j];
                            long dj = tup.Item1;
                            int nj = tup.Item2;
                            exprb2 += (((di * dj) % c_mod) * ni * nj) % c_mod;
                        }
                        // Products of pair of combination and remaining items
                        for (int j = ilo; j < child_count; ++j) {
                            exprb2 += (((di * Links[j].SubDown) % c_mod) * ni) % c_mod;
                        }
                    }
                }
                
                // Remaining pairs, not in stored combinations
                for (int i = ilo + 1; i < child_count; ++i) {
                    long di = Links[i].SubDown;
                    for (int j = ilo; j < i; ++j) {
                        exprb2 += (di * Links[j].SubDown) % c_mod;
                    }
                }

                SubBelow = (int)((exprb1 + 2 * exprb2) % c_mod);
                SubDown = (int)((2 * exprd + 1) % c_mod);
            }        
        }

        public int CompareTo(object obj)
        {
            return SubDown.CompareTo(((Node)obj).SubDown);
        }
    }

    class VPath {
        const char c_zero = '0';
        const int c_mod = 1000000007;

        static void Main()
        {
            // Number of tests
            int space_i;
            string str_in = Console.ReadLine();
            int t = StringToInt(str_in, 0, out space_i);
            while (t-- > 0) {
                // Read N
                str_in = Console.ReadLine();
                int n = StringToInt(str_in, 0, out space_i);

                // Initialise nodes
                Node[] nodes = new Node[n];
                int i;
                for (i = 0; i < n; ++i) {
                    nodes[i] = new Node();
                }

                // Read links between nodes
                int n1 = n - 1;
                for (i = 0; i < n1; ++i) {
                    str_in = Console.ReadLine();
                    Node u = nodes[StringToInt(str_in, 0, out space_i) - 1];  // - 1 for 0-based indexes
                    Node v = nodes[StringToInt(str_in, space_i + 1, out space_i) - 1];
                    u.Links.Add(v);
                    v.Links.Add(u);
                }

                // Evaluate parents of all nodes, set levels, working through tree by DFS.
                // Return list of nodes on each level.
                Node root = nodes[0];  // chosen arbitrarily)
                List<List<Node>> levels = EvaluateParentsLevels(root);

                // Work up the levels, setting SubTree.
                // Omit last level, containing only leaves

                for (int level = levels.Count - 2; level >= 0; --level) {
                    List<Node> nodes_on_level = levels[level];
                    for (i = nodes_on_level.Count - 1; i >= 0; --i) {
                        nodes_on_level[i].EvaluateSubTotals();
                    }
                }

                int result = root.SubBelow + root.SubDown;
                if (result >= c_mod)
                    result -= c_mod;
                Console.WriteLine(result);
            }
        }

        private static List<List<Node>> EvaluateParentsLevels(Node root)
        // Evaluate parents of all nodes, set levels, working through tree by DFS.
        // Return list of nodes on each level.
        {
            List<List<Node>> levels = new List<List<Node>>();
            root.Level = 0;
            root.Parent = null;
            Stack<Node> stack = new Stack<Node>();
            stack.Push(root);
            while (stack.Count > 0) {
                Node node_here = stack.Pop();
                Node node_above = node_here.Parent;
                int depth_here = node_here.Level;
                int depth_n = depth_here + 1;
                List<Node> links = node_here.Links;
                for (int j = links.Count - 1; j >= 0; --j) {
                    Node child = links[j];
                    if (child == node_above) {
                        links.RemoveAt(j);
                    } else {
                        child.Parent = node_here;
                        child.Level = depth_n;
                        stack.Push(child);
                    }
                }
                if (levels.Count == depth_here) {
                    levels.Add(new List<Node> { node_here });
                } else {
                    levels[depth_here].Add(node_here);
                }
            }
            return levels;
        }

        private static int StringToInt(string s, int index, out int space_i)
        // Convert string from index up to next space or end to integer.
        // Return space_i = index of next space encountered, or off end of string.
        {
            int n = s[index] - c_zero;
            int len = s.Length;
            while (++index < len) {
                if (s[index] < c_zero)
                    break;
                n = n * 10 + (s[index] - c_zero);
            }
            space_i = index;
            return n;
        }
    }
}

Valid Paths CodeChef Solution in GO

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)

func myPrintln(a ...interface{}) { _, _ = fmt.Fprintln(writer, a...) }

const MOD = 1000000007

func main() {
	defer func() {
		_ = writer.Flush()
	}()

	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024), 1<<30)

	T := NextInt()
	for t := 0; t < T; t++ {
		ValidPaths()
	}
}

type Graph struct {
	Head      map[int]int
	Next      []int
	Connected []int
	Visited   map[int]struct{}
}

func (g *Graph) AddConnection(u, v int) {
	head, ok := g.Head[u]
	if ok == false {
		head = -1
	}
	g.Connected = append(g.Connected, v)
	g.Next = append(g.Next, head)
	g.Head[u] = len(g.Next) - 1
}

func (g *Graph) DFS(node int, before func(node int), after func(node, child int)) {
	g.Visited[node] = struct{}{}

	before(node)

	head, ok := g.Head[node]
	if ok == false {
		head = -1
	}
	for i := head; i != -1; i = g.Next[i] {
		v := g.Connected[i]
		if _, ok := g.Visited[v]; ok {
			continue
		}
		g.DFS(v, before, after)

		after(node, v)
	}
}

func NewGraph() *Graph {
	return &Graph{
		Head: make(map[int]int),
	}
}

func ValidPaths() {
	n := NextInt()
	tree := NewGraph()
	for i := 1; i < n; i++ {
		u, v := NextInt(), NextInt()
		tree.AddConnection(u, v)
		tree.AddConnection(v, u)
	}

	ans := int64(0)
	val := make([]int64, n+1)

	tree.Visited = make(map[int]struct{})
	tree.DFS(1, func(node int) {
		val[node] = 1
	}, func(node, child int) {
		ans += val[child] * (val[node] - 1) % MOD
		val[node] += val[child] * 2 % MOD
	})

	myPrintln((ans + val[1]) % MOD)
}

func NextInt() int {
	scanner.Scan()
	ret, _ := strconv.Atoi(scanner.Text())
	return ret
}
Valid Paths CodeChef Solution Review:

In our experience, we suggest you solve this Valid Paths CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Valid Paths CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Valid Paths CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *