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 ansValid 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.
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!
