Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Subtree Removal CodeChef Solution

Problem -Subtree Removal 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.

Subtree RemovalCodeChef Solution in C++17

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;

#define all(v)       v.begin(),v.end()
#define sz(x)        (int)(x).size()
#define alr(v)       v.rbegin(),v.rend()
#define pb           push_back
#define S            second
#define F            first
#define pow2(x)      (1<<(x))
#define sp(x)        cout<<fixed<<setprecision(6)<<x
#define output(x)    cout<<(x?"YES\n":"NO\n")
#define bp(x)        __builtin_popcount(x)
//#define int long long
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int inf=2e9;
const int N=2e3+1;
const char nl='\n';
const ll mod=1e9+7;
const ll Binf=1e18;
const ll mod1=998244353;


   
void solve101(){
    ll n,k;cin>>n>>k;
    vector<ll> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<vi> graph(n,vector<int>());
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        u--,v--;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    vector<int> subtr(n,0);
    function<ll(int,int)>dfs=[&](int x,int p){
        ll sum=v[x];
        for(auto it:graph[x]){
            if(it!=p){
                sum+=dfs(it,x);
            }
        }
        ll ans=max(-k,sum);
        return ans;
    };
    cout<<dfs(0,-1)<<nl;
}
signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0); 
    cout.tie(0);
    
    int t=1;
    // debug(pr);
    cin>>t; 
    for(int i=1;i<=t;i++){
        // cout<<"Case #"<<i<<": ";
        solve101();  
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// always check for binary search >.<

// #ifndef ONLINE_JUDGE
//     if (fopen("input.txt", "r"))
//     {
//         freopen("input.txt", "r", stdin);
//         freopen("output.txt", "w", stdout);
//     }
// #endif

Subtree Removal CodeChef Solution in C++14

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
vector<ll>adj[100005];
ll ans=0;
ll solve(ll i,ll p,vector<ll>&dp,ll &x,ll *a)
{   ll ct=0,g=0;

    for(auto it:adj[i])
    {  if(it!=p)
    {
       ct+=solve(it,i,dp,x,a);
       g+=dp[it];
    }
    }
    ct+=a[i];
    dp[i]=max(dp[i],max(-1*ct-x,g));
   // cout<<i<<" "<<dp[i]<<" "<<ct<<" "<<g<<endl;
    return ct;
}
int main() 
{
	
	ll t,m,n,i,j,k,p,q,x;
	cin>>t;
	while(t--)
	{
	    cin>>n>>x;
	    ll a[n+1];
	    ans=0;
	    for(i=1;i<=n;i++)
	    {
	    cin>>a[i];
	    ans+=a[i];
	    }
	    for(i=0;i<n-1;i++)
	    {
	        cin>>p>>q;
	        adj[p].push_back(q);
	        adj[q].push_back(p);
	    }
	    vector<ll>dp(n+1,0);
	    solve(1LL,-1LL,dp,x,a);
	    cout<<ans+dp[1]<<endl;
	    for(i=1;i<=n;i++)
	    adj[i].clear();
	}
	return 0;
}

Subtree Removal CodeChef Solution in PYTH 3

# cook your dish here
import sys
sys.setrecursionlimit(100000)
def dfs(node,tree,par,X,values):
    res = 0
    for edge in tree[node]:
        if edge==par:
            continue
        res+=dfs(edge,tree,node,X,values)
    return max(values[node]+res,-X)
    

T = int(input())
for _ in range(T):
    N,X = tuple(map(int,input().split()))
    values = list(map(int,input().split()))
    tree = [[] for _ in range(N)]
    for _ in range(N-1):
        i,j = tuple(map(int,input().split()))
        tree[i-1].append(j-1)
        tree[j-1].append(i-1)
    print(dfs(0,tree,-1,X,values))

Subtree Removal CodeChef Solution in C

#include <stdio.h>
#include <stdlib.h>
struct Node{
    int val;
    struct Node * next;
};
long int dfs(struct Node** graph,int* g,int a,int b,long int x){
    long int dp = 0;
    while (graph[a]!=NULL){
        if (graph[a]->val!=b){
            dp = dp + dfs(graph,g,graph[a]->val,a,x);
        }
        graph[a] = graph[a]->next;
    }
    if (g[a]+dp>-x){
        return g[a]+dp;
    }
    return -x;
}
int main(void) {
	// your code goes here
	int T;
	scanf("%d",&T);
	while(T--){
	    long int N,X;
	    scanf("%ld %ld",&N,&X);
	    struct Node* graph[N];
	    for (int i=0;i<N;i++){
	        graph[i] = NULL;
	    }
	    int g[N];
	    for (int i=0;i<N;i++){
	        scanf("%d",&g[i]);
	    }
	    for (int i=1;i<N;i++){
	        int x,y;
	        scanf("%d %d",&x,&y);
	        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); 
            newNode->val = y-1; 
	        newNode->next = graph[x-1];
	        graph[x-1] = newNode;
	        struct Node* newNode1 = (struct Node*) malloc(sizeof(struct Node)); 
            newNode1->val = x-1; 
	        newNode1->next = graph[y-1];
	        graph[y-1] = newNode1;
	    }
	    long int d = dfs(graph,g,0,0,X);
	    printf("%ld\n",d);
	}
	return 0;
}


Subtree Removal CodeChef Solution in JAVA

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

import java.io.*;
import java.math.BigInteger;
import java.util.*;

class InputReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public static InputReader getInputReader(boolean readFromTextFile) throws FileNotFoundException {
        return ((readFromTextFile) ? new InputReader(new FileInputStream("src/com/kickStart/input.text"))
                : new InputReader(System.in));
    }

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1) {
            return -1;
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            if (Character.isValidCodePoint(c)) {
                res.appendCodePoint(c);
            }
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuilder buf = new StringBuilder();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r') {
                buf.appendCodePoint(c);
            }
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0) {
            s = readLine0();
        }
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines) {
            return readLine();
        } else {
            return readLine0();
        }
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(nextString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char nextCharacter() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        return (char) c;
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1) {
            read();
        }
        return value == -1;
    }

    public String next() {
        return nextString();
    }

    public SpaceCharFilter getFilter() {
        return filter;
    }

    public void setFilter(SpaceCharFilter filter) {
        this.filter = filter;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }

    public int[] nextIntArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; ++i) array[i] = nextInt();
        return array;
    }

    public int[] nextSortedIntArray(int n) {
        int array[] = nextIntArray(n);
        Arrays.sort(array);
        return array;
    }

    public int[] nextSumIntArray(int n) {
        int[] array = new int[n];
        array[0] = nextInt();
        for (int i = 1; i < n; ++i) array[i] = array[i - 1] + nextInt();
        return array;
    }

    public long[] nextLongArray(int n) {
        long[] array = new long[n];
        for (int i = 0; i < n; ++i) array[i] = nextLong();
        return array;
    }

    public long[] nextSumLongArray(int n) {
        long[] array = new long[n];
        array[0] = nextInt();
        for (int i = 1; i < n; ++i) array[i] = array[i - 1] + nextInt();
        return array;
    }

    public long[] nextSortedLongArray(int n) {
        long array[] = nextLongArray(n);
        Arrays.sort(array);
        return array;
    }

    public long[] getArray(int size, long val) {
        long[] arr = new long[size];
        for (int i = 0; i < size; i++) {
            arr[i] = val;
        }
        return arr;
    }

    public int[] getArray(int size, int val) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = val;
        }
        return arr;
    }
    public double[] getArray(int size, double val) {
        double[] arr = new double[size];
        for (int i = 0; i < size; i++) {
            arr[i] = val;
        }
        return arr;
    }

    public boolean[] getArray(int size,boolean val) {
        boolean[] arr = new boolean[size];
        for (int i = 0; i < size; i++) {
            arr[i] = val;
        }
        return arr;
    }

}

class Graph {
    int n;
    private List<Integer>[] adj;

    /**
     * 0 based index size.
     * @param n size of graph.
     */
    Graph(int n){
        this.n = n;
        adj = new List[n];
        for(int i=0;i<n;i++){
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int a,int b) {
        adj[a].add(b);
        adj[b].add(a);
    }


    public List<Integer>[] getAdj() {
        return adj;
    }
}

class CodeChef {
    public static void main(String[] args) throws IOException {
        Solver solver = new Solver();
        solver.solve();
    }
}

class Solver {
    long res  = 0;

    public void solve() throws FileNotFoundException {
        boolean readFromLocal = false;
        //readFromLocal = true;
        InputReader inputReader = InputReader.getInputReader(readFromLocal);
        int t = inputReader.nextInt();
        while (t > 0) {
            t--;
            res = 0;
            int n = inputReader.nextInt();
            long x = inputReader.nextInt();
            long[] val = inputReader.nextLongArray(n);
            Graph g = new Graph(n+1);
            for(int i =0;i<n-1;i++) {
                g.addEdge(inputReader.nextInt(), inputReader.nextInt());
            }
            long[] dp = inputReader.getArray(n+1, -x);
            boolean[] vis = inputReader.getArray(n+1,false);
            System.out.println(dfs(1,g,val,dp,vis));
        }
    }

    private long  dfs(int root, Graph g, long[] val, long[] dp, boolean[] vis) {
        long sum = val[root-1];
        vis[root] = true;
        for (int child: g.getAdj()[root]) {
            if (!vis[child]) {
                dfs(child, g, val, dp, vis);
                sum += dp[child];
            }
        }
        return dp[root] = Math.max(sum,dp[root]);
    }

}

Subtree Removal CodeChef Solution in PYTH

t = int(raw_input())
import sys 
sys.setrecursionlimit(10 ** 8)
for _ in xrange(t):
    n, x = map(int, raw_input().split())
    weight = map(int, raw_input().split())
    g = [set() for _ in xrange(n)]
    for _ in range(n-1):
        u, v = map(int, raw_input().split())
        u -= 1 
        v -= 1 
        g[u].add(v) 
        g[v].add(u) 
    
    dp = [float('-inf')] * n
    ans = -x
    def dfs(node, p = None):
        dp[node] = weight[node]
        for i in g[node]:
            if i != p:
                dfs(i, node) 
                dp[node] += dp[i]
        dp[node] = max(dp[node], -x)
    dfs(0) 
    print (dp[0])
            
        

Subtree Removal CodeChef Solution in C#

#region Usings
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using static System.Array;
using static System.Math;

// ReSharper disable InconsistentNaming
#pragma warning disable CS0675
#endregion

partial class Solution
{
    #region Variables
    const int MOD = 1000000007;
    const int FactCache = 1000;
    const long BIG = long.MaxValue >> 15;

    #endregion

    public void Solve()
    {
        int T = Ni();

        for (int t = 1; t <= T; t++)
        {
            int N = Ni();
            long X = Nl();
            var A = Nl(N, 1);

            var scores = new long[N + 1];
            var g = NewGraph(N, N - 1);

            var tree = new TreeGraph(g, 1);
            for (int iu = tree.TreeSize - 1; iu >= 0; iu--)
            {
                int u = tree.Trace[iu];
                int p = tree.Parent[u];
                long score = A[u];
                foreach (var v in g[u])
                {
                    if (v == p) continue;
                    score += scores[v];
                }

                if (score < -X) score = -X;
                scores[u] = score;
            }


            WriteLine(scores[1]);
        }
    }
    
    public class TreeGraph
    {
        #region Variables
        public List<int>[] Graph;
        public int[] Sizes;
        public int[] Begin;
        public int[] Parent;
        public int[] Head;
        public int[] Trace;
        public int TreeSize;
        public int Root => Trace[0];
        public int End(int v) => Begin[v] + Sizes[v] - 1;
        #endregion

        #region Construction
        public TreeGraph(List<int>[] graph, int root = 0, int avoid = -1)
        {
            Graph = graph;
            int n = graph.Length;
            Sizes = new int[n];
            Begin = new int[n];
            Head = new int[n];
            Trace = new int[n];
            Parent = new int[n];
            Build(root, avoid);
        }

        unsafe void Build(int r = 0, int avoid = -1)
        {
            var stack = stackalloc int[Graph.Length + 1];
            int stackSize = 0, treeSize = 0;
            stack[stackSize++] = r;
            Parent[r] = -1;
            while (stackSize > 0)
            {
                var u = stack[--stackSize];
                Trace[treeSize++] = u;
                Head[u] = u;
                Sizes[u] = 1;
                foreach (var v in Graph[u])
                {
                    if (Sizes[v] > 0 || v == avoid) continue;
                    Parent[v] = u;
                    stack[stackSize++] = v;
                }
            }

            for (int iu = treeSize - 1; iu >= 0; iu--)
            {
                var u = Trace[iu];
                var p = Parent[u];
                var neighbors = Graph[u];
                int maxSize = 0;
                for (var i = 0; i < neighbors.Count; i++)
                {
                    var v = neighbors[i];
                    if (v != p && v != avoid)
                    {
                        Sizes[u] += Sizes[v];
                        if (Sizes[v] > maxSize)
                        {
                            maxSize = Sizes[v];
                            neighbors[i] = neighbors[0];
                            neighbors[0] = v;
                        }
                    }
                }
            }

            stackSize = treeSize = 0;
            stack[stackSize++] = r;
            while (stackSize > 0)
            {
                var u = stack[--stackSize];
                Begin[u] = treeSize;
                Trace[treeSize++] = u;
                int heavy = -1;
                var children = Graph[u];
                for (int iv = children.Count - 1; iv >= 0; iv--)
                {
                    var v = children[iv];
                    if (v != Parent[u] && v != avoid)
                        stack[stackSize++] = heavy = v;
                }
                if (heavy >= 0) Head[heavy] = Head[u];
            }

            TreeSize = treeSize;
        }
        #endregion

        #region LCA
        public int Lca(int x, int y)
        {
            int diff = Begin[y] - Begin[x];
            if (diff >= 0) { if (diff < Sizes[x]) return x; }
            else { if (-diff < Sizes[y]) return y; }

            for (int rx = Head[x], ry = Head[y]; rx != ry;)
            {
                if (Begin[rx] > Begin[ry])
                {
                    x = Parent[rx];
                    rx = Head[x];
                }
                else
                {
                    y = Parent[ry];
                    ry = Head[y];
                }
            }
            return Begin[x] > Begin[y] ? y : x;
        }

        public int Distance(int x, int y)
        {
            var distance = 0;
            for (int rx = Head[x], ry = Head[y]; rx != ry;)
            {
                if (Begin[rx] > Begin[ry])
                {
                    distance += 1 + Begin[x] - Begin[rx];
                    x = Parent[rx];
                    rx = Head[x];
                }
                else
                {
                    distance += 1 + Begin[y] - Begin[ry];
                    y = Parent[ry];
                    ry = Head[y];
                }
            }
            return distance + Abs(Begin[x] - Begin[y]);
        }

        public int Ancestor(int x, int v)
        {
            while (x >= 0)
            {
                int position = Begin[x] - Begin[Head[x]];
                if (v <= position) return Trace[Begin[x] - v];
                v -= position + 1;
                x = Parent[Head[x]];
            }
            return x;
        }

        public int Advance(int source, int dest)
        {
            int sourceIndex = Begin[source];
            while (sourceIndex < Begin[dest])
            {
                if (Head[source] != Head[dest])
                {
                    dest = Head[dest];
                    var parent = Parent[dest];
                    if (parent == source) return dest;
                    dest = parent;
                }
                else
                {
                    return Trace[sourceIndex + 1];
                }
            }

            return Parent[source];
        }

        public int Intersect(int p1, int p2, int p3)
        {
            if (Begin[p1] > Begin[p2]) Swap(ref p1, ref p2);
            if (Begin[p2] > Begin[p3]) Swap(ref p2, ref p3);
            if (Begin[p1] > Begin[p2]) Swap(ref p1, ref p2);

            if (unchecked((uint)(Begin[p3] - Begin[p2]) < (uint)Sizes[p2]))
                return p2;

            var lca = Lca(p1, p2);
            return unchecked((uint)(Begin[p3] - Begin[lca]) >= (uint)Sizes[lca])
                ? lca : Lca(p2, p3);
        }

        #endregion

        #region HLD
        List<Segment> segs = new List<Segment>(32);
        Segment[] segs2 = new Segment[32];
        public List<Segment> Query(int x, int y, bool edges = false)
        {
            // up segs in ascending order, down segs in descending order
            segs.Clear();

            int crev = 0;
            for (int rx = Head[x], ry = Head[y]; rx != ry;)
            {
                if (Begin[rx] > Begin[ry])
                {
                    segs.Add(new Segment(Begin[rx], Begin[x], 1));
                    x = Parent[rx];
                    rx = Head[x];
                }
                else
                {
                    segs2[crev++] = new Segment(Begin[ry], Begin[y], -1);
                    y = Parent[ry];
                    ry = Head[y];
                }
            }

            var lcaIndex = Min(Begin[x], Begin[y]);
            var nodeIndex = Max(Begin[x], Begin[y]);
            if (edges == false || lcaIndex < nodeIndex)
                segs.Add(new Segment(lcaIndex + (edges ? 1 : 0), nodeIndex,
                    nodeIndex == Begin[x] ? 1 : -1));

            while (crev > 0) segs.Add(segs2[--crev]);
            return segs;
        }

        public struct Segment
        {
            public int HeadIndex, NodeIndex, Dir;
            public Segment(int headIndex, int nodeIndex, int dir)
            {
                HeadIndex = headIndex;
                NodeIndex = nodeIndex;
                Dir = dir;
            }
        }
        #endregion

    }

    #region Library
    #region Mod Math

    static int[] _inverse;
    static long Inverse(long n)
    {
        long result;

        if (_inverse == null)
            _inverse = new int[1000];

        if (n >= 0 && n < _inverse.Length && (result = _inverse[n]) != 0)
            return result - 1;

        result = InverseDirect((int)n);
        if (n >= 0 && n < _inverse.Length)
            _inverse[n] = (int)(result + 1);
        return result;
    }

    public static int InverseDirect(int a)
    {
        if (a < 0) return -InverseDirect(-a);
        int t = 0, r = MOD, t2 = 1, r2 = a;
        while (r2 != 0)
        {
            var q = r / r2;
            t -= q * t2;
            r -= q * r2;

            if (r != 0)
            {
                q = r2 / r;
                t2 -= q * t;
                r2 -= q * r;
            }
            else
            {
                r = r2;
                t = t2;
                break;
            }
        }
        return r <= 1 ? (t >= 0 ? t : t + MOD) : -1;
    }

    static long Mult(long left, long right) =>
        (left * right) % MOD;

    static long Div(long left, long divisor) =>
        left * Inverse(divisor) % MOD;

    static long Add(long x, long y) =>
        (x += y) >= MOD ? x - MOD : x;

    static long Subtract(long x, long y) => (x -= y) < 0 ? x + MOD : x;

    static long Fix(long n) => (n %= MOD) >= 0 ? n : n + MOD;

    static long ModPow(long n, long p, long mod = MOD)
    {
        long b = n;
        long result = 1;
        while (p != 0)
        {
            if ((p & 1) != 0)
                result = (result * b) % mod;
            p >>= 1;
            b = (b * b) % mod;
        }
        return result;
    }

    static List<long> _fact;

    static long Fact(int n)
    {
        if (_fact == null) _fact = new List<long>(FactCache) { 1 };
        for (int i = _fact.Count; i <= n; i++)
            _fact.Add(Mult(_fact[i - 1], i));
        return _fact[n];
    }

    static long[] _ifact = new long[0];
    static long InverseFact(int n)
    {
        long result;
        if (n < _ifact.Length && (result = _ifact[n]) != 0)
            return result;

        var inv = Inverse(Fact(n));
        if (n >= _ifact.Length) Resize(ref _ifact, _fact.Capacity);
        _ifact[n] = inv;
        return inv;
    }

    static long Fact(int n, int m)
    {
        var fact = Fact(n);
        if (m < n) fact = fact * InverseFact(n - m) % MOD;
        return fact;
    }

    static long Comb(int n, int k)
    {
        if (k <= 1) return k == 1 ? n : k == 0 ? 1 : 0;
        return Mult(Mult(Fact(n), InverseFact(k)), InverseFact(n - k));
    }

    public static long Combinations(long n, int k)
    {
        if (k <= 0) return k == 0 ? 1 : 0;  // Note: n<0 -> 0 unless k=0
        if (k + k > n) return Combinations(n, (int)(n - k));

        var result = InverseFact(k);
        for (long i = n - k + 1; i <= n; i++) result = result * i % MOD;
        return result;
    }
    #endregion

    #region Common
    partial void TestData();

    static void Swap<T>(ref T a, ref T b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }

    static int Bound<T>(T[] array, T value, bool upper = false)
        where T : IComparable<T>
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left >> 1);
            int cmp = value.CompareTo(array[mid]);
            if (cmp > 0 || cmp == 0 && upper)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    static int Gcd(int n, int m)
    {
        while (true)
        {
            if (m == 0) return n >= 0 ? n : -n;
            n %= m;
            if (n == 0) return m >= 0 ? m : -m;
            m %= n;
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static unsafe int Log2(long value)
    {
        double f = unchecked((ulong)value); // +.5 -> -1 for zero
        return (((int*)&f)[1] >> 20) - 1023;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static int BitCount(long y)
    {
        var x = unchecked((ulong)y);
        x -= (x >> 1) & 0x5555555555555555;
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
        return unchecked((int)((x * 0x0101010101010101) >> 56));
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static int HighestOneBit(int n) => n != 0 ? 1 << Log2(n) : 0;
    /*static unsafe int HighestOneBit(int x) // sometimes doesn't work
	{
		double f = unchecked((uint)x);
        return unchecked(1 << (((int*)&f)[1] >> 20) - 1023 & ~((x - 1 & -x - 1) >> 31));
	}*/

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static unsafe long HighestOneBit(long x)
    {
        double f = unchecked((ulong)x);
        return unchecked(1L << (((int*)&f)[1] >> 20) - 1023 & ~(x - 1 >> 63 & -x - 1 >> 63));
    }
    #endregion

    #region Fast IO
    #region  Input
    static Stream inputStream;
    static int inputIndex, bytesRead;
    static byte[] inputBuffer;
    static StringBuilder builder;
    const int MonoBufferSize = 4096;
    const char EOL = (char)10, DASH = (char)45, ZERO = (char)48;

    static void InitInput(Stream input = null, int stringCapacity = 16)
    {
        builder = new StringBuilder(stringCapacity);
        inputStream = input ?? Console.OpenStandardInput();
        inputIndex = bytesRead = 0;
        inputBuffer = new byte[MonoBufferSize];
    }

    static void ReadMore()
    {
        if (bytesRead < 0) throw new FormatException();
        inputIndex = 0;
        bytesRead = inputStream.Read(inputBuffer, 0, inputBuffer.Length);
        if (bytesRead > 0) return;
        bytesRead = -1;
        inputBuffer[0] = (byte)EOL;
    }

    static int Read()
    {
        if (inputIndex >= bytesRead) ReadMore();
        return inputBuffer[inputIndex++];
    }

    static T[] Na<T>(int n, Func<T> func, int z = 0)
    {
        n += z;
        var list = new T[n];
        for (int i = z; i < n; i++) list[i] = func();
        return list;
    }

    static int[] Ni(int n, int z = 0) => Na(n, Ni, z);

    static long[] Nl(int n, int z = 0) => Na(n, Nl, z);

    static string[] Ns(int n, int z = 0) => Na(n, Ns, z);

    static int Ni() => checked((int)Nl());

    static long Nl()
    {
        var c = SkipSpaces();
        bool neg = c == DASH;
        if (neg) { c = Read(); }

        long number = c - ZERO;
        while (true)
        {
            var d = Read() - ZERO;
            if (unchecked((uint)d > 9)) break;
            number = number * 10 + d;
            if (number < 0) throw new FormatException();
        }
        return neg ? -number : number;
    }

    static char[] Nc(int n)
    {
        var list = new char[n];
        for (int i = 0, c = SkipSpaces(); i < n; i++, c = Read()) list[i] = (char)c;
        return list;
    }

    static string Ns()
    {
        var c = SkipSpaces();
        builder.Clear();
        while (true)
        {
            if (unchecked((uint)c - 33 >= (127 - 33))) break;
            builder.Append((char)c);
            c = Read();
        }
        return builder.ToString();
    }

    static int SkipSpaces()
    {
        int c;
        do c = Read(); while (unchecked((uint)c - 33 >= (127 - 33)));
        return c;
    }

    static List<int>[] NewGraph(int n, int m = 0, int off = 0)
    {
        n += 1 + off;
        var g = new List<int>[n];
        for (int i = 0; i < n; i++)
            g[i] = new List<int>();

        for (int i = 0; i < m; i++)
        {
            int u = Ni() + off, v = Ni() + off;
            g[u].Add(v);
            g[v].Add(u);
        }

        return g;
    }

    static string ReadLine()
    {
        builder.Clear();
        while (true)
        {
            int c = Read();
            if (c < 32) { if (c == 10 || c <= 0) break; continue; }
            builder.Append((char)c);
        }
        return builder.ToString();
    }
    #endregion

    #region Output
    static Stream outputStream;
    static byte[] outputBuffer;
    static int outputIndex;

    static void InitOutput(Stream output = null)
    {
        outputStream = output ?? Console.OpenStandardOutput();
        outputIndex = 0;
        outputBuffer = new byte[65535];
    }

    static void WriteLine(object obj = null)
    {
        Write(obj);
        Write(EOL);
    }

    static void WriteLine(long number)
    {
        Write(number);
        Write(EOL);
    }

    static void Write(long signedNumber)
    {
        ulong number = unchecked((ulong)signedNumber);
        if (signedNumber < 0)
        {
            Write(DASH);
            number = unchecked((ulong)(-signedNumber));
        }

        Reserve(20 + 1); // 20 digits + 1 extra for sign
        int left = outputIndex;
        do
        {
            outputBuffer[outputIndex++] = (byte)(ZERO + number % 10);
            number /= 10;
        }
        while (number > 0);

        int right = outputIndex - 1;
        while (left < right)
        {
            byte tmp = outputBuffer[left];
            outputBuffer[left++] = outputBuffer[right];
            outputBuffer[right--] = tmp;
        }
    }

    static void Write(object obj)
    {
        if (obj == null) return;

        var s = obj.ToString();
        Reserve(s.Length);
        for (int i = 0; i < s.Length; i++)
            outputBuffer[outputIndex++] = (byte)s[i];
    }

    static void Write(char c)
    {
        Reserve(1);
        outputBuffer[outputIndex++] = (byte)c;
    }

    static void Write(byte[] array, int count)
    {
        Reserve(count);
        Copy(array, 0, outputBuffer, outputIndex, count);
        outputIndex += count;
    }

    static void Reserve(int n)
    {
        if (outputIndex + n <= outputBuffer.Length)
            return;

        Dump();
        if (n > outputBuffer.Length)
            Resize(ref outputBuffer, Max(outputBuffer.Length * 2, n));
    }

    static void Dump()
    {
        outputStream.Write(outputBuffer, 0, outputIndex);
        outputIndex = 0;
    }

    static void Flush()
    {
        Dump();
        outputStream.Flush();
    }

    #endregion
    #endregion

    #region Main

    public static void Main()
    {
        AppDomain.CurrentDomain.UnhandledException += (sender, arg) =>
        {
            Flush();
            var e = (Exception)arg.ExceptionObject;
            Console.Error.WriteLine(e);
            var line = new StackTrace(e, true).GetFrames()
                .Select(x => x.GetFileLineNumber()).FirstOrDefault(x => x != 0);
            var wait = line % 300 * 10 + 5;
            var process = Process.GetCurrentProcess();
            while (process.TotalProcessorTime.TotalMilliseconds > wait && wait < 3000) wait += 1000;
            while (process.TotalProcessorTime.TotalMilliseconds < Min(wait, 3000)) ;
            Environment.Exit(1);
        };

        InitInput(Console.OpenStandardInput());
        InitOutput(Console.OpenStandardOutput());
#if __MonoCS__ && !C7
        var thread = new System.Threading.Thread(()=>new Solution().Solve());
        var f = BindingFlags.NonPublic | BindingFlags.Instance;
        var t = thread.GetType().GetField("internal_thread", f).GetValue(thread);
        t.GetType().GetField("stack_size", f).SetValue(t, 32 * 1024 * 1024);
        thread.Start();
        thread.Join();
#else
        new Solution().Solve();
#endif
        Flush();
        Console.Error.WriteLine(Process.GetCurrentProcess().TotalProcessorTime);
    }
    #endregion
    #endregion
}
Subtree Removal CodeChef Solution Review:

In our experience, we suggest you solve this Subtree Removal 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 Subtree Removal CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Subtree Removal 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 *