E - Path Decomposition of a Tree
Source: atcoder
Difficulty: 475

Problem Statement
You are given a tree with
NK
vertices. The vertices are numbered
1,2,\dots,NK
, and the
i
-th edge (
i=1,2,\dots,NK-1
) connects vertices
u_i
and
v_i
bidirectionally.
Determine whether this tree can be decomposed into
N
paths, each of length
K
. More precisely, determine whether there exists an
N \times K
matrix
P
satisfying the following:
P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K}
is a permutation of
1,2,\dots,NK
.
For each
i=1,2,\dots,N
and
j=1,2,\dots,K-1
, there is an edge connecting vertices
P_{i,j}
and
P_{i,j+1}
.
Constraints
1 \leq N
1 \leq K
NK \leq 2 \times 10^5
1 \leq u_i < v_i \leq NK
The given graph is a tree.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
K
u_1
v_1
u_2
v_2
\vdots
u_{NK-1}
v_{NK-1}
Output
If it is possible to decompose the tree into
N
paths each of length
K
, print
Yes
. Otherwise, print
No
.
Sample Input 1
3 2
1 2
2 3
3 4
2 5
5 6
Sample Output 1
Yes
It can be decomposed into a path with vertices
1,2
, a path with vertices
3,4
, and a path with vertices
5,6
.
Sample Input 2
3 2
1 2
2 3
3 4
2 5
3 6
Sample Output 2
No

C++ solution:
#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) (x)&(-x)
#define small priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>
using namespace std;
const int MAXN=200000+5;
vector<int>a[MAXN];
int son[MAXN],n,k;
vector<int>b[MAXN];

void dfs(int x,int fa)
{
	son[x]=1;
	for(int i=0;i<a[x].size();i++)
	{
		if(a[x][i]==fa) continue;
		dfs(a[x][i],x);
		son[x]+=son[a[x][i]];
		b[x].push_back(son[a[x][i]]);
	}
	int flag=0;
	for(int i=0;i<b[x].size();i++)
	{
    // 计算有贡献的儿子的个数
		if(b[x][i]>0)
		{
			flag++;
		}
	}
	if(son[x]==k) 
	{
		if(flag>2) 
		{
			cout<<"No\n";
			exit(0);
		}
		son[x]=0;
		return ;
	}
	if(flag<=1) return ;
	cout<<"No\n";
	exit(0);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	int x,y;
	for(int i=1;i<n*k;i++)
	{
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);	
	}
	dfs(1,-1);
	if(son[1]!=0) cout<<"No\n";
	else cout<<"Yes\n";
	return 0;
}

Go solution:
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	//bufサイズ以上の文字列入力が必要な場合は拡張すること
	buf := make([]byte, 9*1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)

	n, k := nextInt(), nextInt()
	var u, v []int
	for i := 0; i < n*k-1; i++ {
		u = append(u, nextInt()-1)
		v = append(v, nextInt()-1)
	}

	if solve(n, k, u, v) {
		Print("Yes")
	} else {
		Print("No")
	}
}

func solve(n, k int, u, v []int) bool {
	e := make([][]int, n*k)
	m := n*k - 1
	for i := 0; i < m; i++ {
		e[u[i]] = append(e[u[i]], v[i])
		e[v[i]] = append(e[v[i]], u[i])
	}
	decomposed := make([]bool, n*k)
	l := make([]int, n*k)
	var dfs func(cur, par int) bool
	dfs = func(cur, par int) bool {
		ok := true
		var numChildren int
		for _, next := range e[cur] {
			if next == par {
				continue
			}
			ok = ok && dfs(next, cur)
			if !decomposed[next] {
				numChildren++
			}
		}
		if !ok {
			return false
		}
		switch numChildren {
		case 0:
			l[cur]++
			if l[cur] == k {
				decomposed[cur] = true
			}
			return true
		case 1:
			l[cur]++
			for _, next := range e[cur] {
				if next == par {
					continue
				}
				if decomposed[next] {
					continue
				}
				l[cur] += l[next]
			}
			if l[cur] == k {
				decomposed[cur] = true
			}
		case 2:
			l[cur]++
			for _, next := range e[cur] {
				if next == par {
					continue
				}
				if decomposed[next] {
					continue
				}
				l[cur] += l[next]
			}
			if l[cur] == k {
				decomposed[cur] = true
			} else {
				return false
			}
		default:
			// numChildren >= 3
			return false
		}
		return true
	}

	ans := dfs(0, -1)
	//fmt.Println(l)
	//fmt.Println(decomposed)
	return ans

}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}

func Print(x any) {
	defer out.Flush()
	fmt.Fprintln(out, x)
}

Java solution:
//package atcoder.abc397;

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

import static java.lang.Math.*;

public class Main {
    static InputReader in;
    static PrintWriter out;

    public static void main(String[] args) {
        //initReaderPrinter(true);
        initReaderPrinter(false);
        //solve(in.nextInt());
        solve(1);
    }  
   
    /*
        General tips
        1. It is ok to fail, but it is not ok to fail for the same mistakes over and over!
        2. Train smarter, not harder!
        3. If you find an answer and want to return immediately, don't forget to flush before return!
    */
    /*
        Read before practice
        1. Set a timer based on a problem's difficulty level: 45 minutes at your current target practice level;
        2. During a problem solving session, focus! Do not switch problems or even worse switch to do something else;
        3. If fail to solve within timer limit, read editorials to get as little help as possible to get yourself unblocked;
        4. If after reading the entire editorial and other people's code but still can not solve, move this problem to to-do list
           and re-try in the future.
        5. Keep a practice log about new thinking approaches, good tricks, bugs; Review regularly;
        6. Also try this new approach suggested by um_nik: Solve with no intention to read editorial.
           If getting stuck, skip it and solve other similar level problems.
           Wait for 1 week then try to solve again. Only read editorial after you solved a problem.
        7. Remember to also submit in the original problem link (if using gym) so that the 1 v 1 bot knows which problems I have solved already.
        8. Form the habit of writing down an implementable solution idea before coding! You've taken enough hits during contests because you
        rushed to coding!
    */
    /*
        Read before contests and lockout 1 v 1
        Mistakes you've made in the past contests:
        1. Tried to solve without going through given test examples -> wasting time on solving a different problem than asked;
        2. Rushed to coding without getting a comprehensive sketch of your solution -> implementation bugs and WA; Write down your idea step
        by step, no need to rush. It is always better to have all the steps considered before hand! Think about all the past contests that
        you have failed because slow implementation and implementation bugs! This will be greatly reduced if you take your time to get a
        thorough idea steps!
        3. Forgot about possible integer overflow;

        When stuck:
        1. Understand problem statements? Walked through test examples?
        2. Take a step back and think about other approaches?
        3. Check rank board to see if you can skip to work on a possibly easier problem?
        4. If none of the above works, take a guess?
        5. Any chance you got WA due to integer overflow, especially if you are dealing with all subarrays. The sum
           can get deceptively large! If in doubt, just use long instead of int.
    */

    static int n, k, remain;
    static int[][] g;
    static void solve(int testCnt) {
        for (int testNumber = 0; testNumber < testCnt; testNumber++) {
            n = in.nextInt();
            k = in.nextInt();
            g = in.buildUndirectedGraph(n * k, n * k - 1);
            remain = n;
            dfs(1, 0);
            out.println(remain <= 0 ? "Yes" : "No");
        }
        out.close();
    }

    static int dfs(int curr, int par) {
        int f1 = 0, f2 = 0;
        for(int next : g[curr]) {
            if(next != par) {
                int cnt = dfs(next, curr);
                if(cnt > f1) {
                    f2 = f1;
                    f1 = cnt;
                }
                else if(cnt > f2) {
                    f2 = cnt;
                }
            }
        }
        if(f1 + f2 + 1 >= k) {
            remain--;
            return 0;
        }
        return f1 + 1;
    }

    static long addWithMod(long x, long y, long mod) {
        return (x + y) % mod;
    }

    static long subtractWithMod(long x, long y, long mod) {
        return ((x - y) % mod + mod) % mod;
    }

    static long multiplyWithMod(long x, long y, long mod) {
        x %= mod;
        y %= mod;
        return x * y % mod;
    }

    static long modInv(long x, long mod) {
        x %= mod;
        return fastPowMod(x, mod - 2, mod);
    }

    static long fastPowMod(long x, long n, long mod) {
        if (n == 0) return 1;
        long half = fastPowMod(x, n / 2, mod);
        if (n % 2 == 0) return half * half % mod;
        return half * half % mod * x % mod;
    }

    static void initReaderPrinter(boolean test) {
        if (test) {
            try {
                in = new InputReader(new FileInputStream("input.in"));
                out = new PrintWriter(new FileOutputStream("output.out"));
            } catch (IOException e) {
                e.printStackTrace();
            }
        } else {
            in = new InputReader(System.in);
            out = new PrintWriter(System.out);
        }
    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        InputReader(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream), 32768);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

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

        int[] nextIntArrayPrimitive(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        int[] nextIntArrayPrimitiveOneIndexed(int n) {
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) a[i] = nextInt();
            return a;
        }

        Long[] nextLongArray(int n) {
            Long[] a = new Long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }

        long[] nextLongArrayPrimitive(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }

        long[] nextLongArrayPrimitiveOneIndexed(int n) {
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++) a[i] = nextLong();
            return a;
        }

        String[] nextStringArray(int n) {
            String[] g = new String[n];
            for (int i = 0; i < n; i++) g[i] = next();
            return g;
        }

        List<Integer>[] readUnWeightedGraphOneIndexed(int n, int m) {
            List<Integer>[] adj = new List[n + 1];
            for (int i = 0; i <= n; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt();
                int v = nextInt();
                adj[u].add(v);
                adj[v].add(u);
            }
            return adj;
        }

        List<int[]>[] readWeightedGraphOneIndexed(int n, int m) {
            List<int[]>[] adj = new List[n + 1];
            for (int i = 0; i <= n; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt();
                int v = nextInt();
                int w = in.nextInt();
                adj[u].add(new int[]{v, w});
                adj[v].add(new int[]{u, w});
            }
            return adj;
        }

        List<Integer>[] readUnWeightedGraphZeroIndexed(int n, int m) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                adj[u].add(v);
                adj[v].add(u);
            }
            return adj;
        }

        List<int[]>[] readWeightedGraphZeroIndexed(int n, int m) {
            List<int[]>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                int w = in.nextInt();
                adj[u].add(new int[]{v, w});
                adj[v].add(new int[]{u, w});
            }
            return adj;
        }

        /*
            A more efficient way of building an undirected graph using int[] instead of ArrayList to store each node's neighboring nodes.
            1-indexed.
         */
        int[][] buildUndirectedGraph(int nodeCnt, int edgeCnt) {
            int[] end1 = new int[edgeCnt], end2 = new int[edgeCnt];
            int[] edgeCntForEachNode = new int[nodeCnt + 1], idxForEachNode = new int[nodeCnt + 1];
            for (int i = 0; i < edgeCnt; i++) {
                int u = in.nextInt(), v = in.nextInt();
                edgeCntForEachNode[u]++;
                edgeCntForEachNode[v]++;
                end1[i] = u;
                end2[i] = v;
            }
            int[][] adj = new int[nodeCnt + 1][];
            for (int i = 1; i <= nodeCnt; i++) {
                adj[i] = new int[edgeCntForEachNode[i]];
            }
            for (int i = 0; i < edgeCnt; i++) {
                adj[end1[i]][idxForEachNode[end1[i]]] = end2[i];
                idxForEachNode[end1[i]]++;
                adj[end2[i]][idxForEachNode[end2[i]]] = end1[i];
                idxForEachNode[end2[i]]++;
            }
            return adj;
        }

        /*
            A more efficient way of building an undirected weighted graph using int[] instead of ArrayList to store each node's neighboring nodes.
            1-indexed.
        */
        int[][][] buildUndirectedWeightedGraph(int nodeCnt, int edgeCnt) {
            int[] end1 = new int[edgeCnt], end2 = new int[edgeCnt], weight = new int[edgeCnt];
            int[] edgeCntForEachNode = new int[nodeCnt + 1], idxForEachNode = new int[nodeCnt + 1];
            for (int i = 0; i < edgeCnt; i++) {
                int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
                edgeCntForEachNode[u]++;
                edgeCntForEachNode[v]++;
                end1[i] = u;
                end2[i] = v;
                weight[i] = w;
            }
            int[][][] adj = new int[nodeCnt + 1][][];
            for (int i = 1; i <= nodeCnt; i++) {
                adj[i] = new int[edgeCntForEachNode[i]][2];
            }
            for (int i = 0; i < edgeCnt; i++) {
                adj[end1[i]][idxForEachNode[end1[i]]][0] = end2[i];
                adj[end1[i]][idxForEachNode[end1[i]]][1] = weight[i];
                idxForEachNode[end1[i]]++;
                adj[end2[i]][idxForEachNode[end2[i]]][0] = end1[i];
                adj[end2[i]][idxForEachNode[end2[i]]][1] = weight[i];
                idxForEachNode[end2[i]]++;
            }
            return adj;
        }

        /*
            A more efficient way of building a directed graph using int[] instead of ArrayList to store each node's neighboring nodes.
            1-indexed.
        */
        int[][] buildDirectedGraph(int nodeCnt, int edgeCnt) {
            int[] from = new int[edgeCnt], to = new int[edgeCnt];
            int[] edgeCntForEachNode = new int[nodeCnt + 1], idxForEachNode = new int[nodeCnt + 1];
            //from u to v: u -> v
            for (int i = 0; i < edgeCnt; i++) {
                int u = in.nextInt(), v = in.nextInt();
                edgeCntForEachNode[u]++;
                from[i] = u;
                to[i] = v;
            }
            int[][] adj = new int[nodeCnt + 1][];
            for (int i = 1; i <= nodeCnt; i++) {
                adj[i] = new int[edgeCntForEachNode[i]];
            }
            for (int i = 0; i < edgeCnt; i++) {
                adj[from[i]][idxForEachNode[from[i]]] = to[i];
                idxForEachNode[from[i]]++;
            }
            return adj;
        }

        /*
            A more efficient way of building a directed weighted graph using int[] instead of ArrayList to store each node's neighboring nodes.
            1-indexed.
        */
        int[][][] buildDirectedWeightedGraph(int nodeCnt, int edgeCnt) {
            int[] from = new int[edgeCnt], to = new int[edgeCnt], weight = new int[edgeCnt];
            int[] edgeCntForEachNode = new int[nodeCnt + 1], idxForEachNode = new int[nodeCnt + 1];
            //from u to v: u -> v
            for (int i = 0; i < edgeCnt; i++) {
                int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
                edgeCntForEachNode[u]++;
                from[i] = u;
                to[i] = v;
                weight[i] = w;
            }
            int[][][] adj = new int[nodeCnt + 1][][];
            for (int i = 1; i <= nodeCnt; i++) {
                adj[i] = new int[edgeCntForEachNode[i]][2];
            }
            for (int i = 0; i < edgeCnt; i++) {
                adj[from[i]][idxForEachNode[from[i]]][0] = to[i];
                adj[from[i]][idxForEachNode[from[i]]][1] = weight[i];
                idxForEachNode[from[i]]++;
            }
            return adj;
        }
    }
}

JavaScript solution:
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const [u, v] = [[], []];
  const G = new Array(N * K).fill(0).map(() => []);
  const deg = new Array(N * K).fill(0);
  for (let i = 0; i < N * K - 1; i++) {
    [u[i], v[i]] = input[i + 1].split(" ").map(Number);
    u[i]--;
    v[i]--;
    G[u[i]].push(v[i]);
    G[v[i]].push(u[i]);
    deg[u[i]]++;
    deg[v[i]]++;
  }

  const seen = new Array(N * K).fill(false);
  const dp = new Array(N * K).fill(1);
  let ans = true;
  const dfs = (v) => {
    seen[v] = true;
    if (!ans) return;

    for (const nv of G[v]) {
      if (seen[nv]) continue;
      dfs(nv);
      dp[v] += dp[nv];
    }

    if (dp[v] > K) ans = false;
    else if (dp[v] == K) {
      if (deg[v] > 3) ans = false;
      else {
        dp[v] = 0;
        for (const nv of G[v]) deg[nv]--;
      }
    } else {
      if (deg[v] > 2) ans = false;
    }

    return;
  };

  dfs(0);
  console.log(ans ? "Yes" : "No");
}
class Node {
  constructor(value = "") {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}
class Deque {
  constructor(arr = []) {
    this.nil = new Node();
    (this.nil.next = this.nil), (this.nil.prev = this.nil);
    for (const value of arr) this.append(value);
    this._cnt = arr.length;
  }

  appendleft(value) {
    const node = new Node(value);
    node.next = this.nil.next;
    node.prev = this.nil;
    this.nil.next.prev = this.nil.next = node;
    this._cnt++;
  }

  append(value) {
    const node = new Node(value);
    (node.prev = this.nil.prev), (node.next = this.nil);
    this.nil.prev.next = this.nil.prev = node;
    this._cnt++;
  }

  pop() {
    const node = this.nil.prev;
    if (node.value === "") return null;
    (node.prev.next = this.nil), (this.nil.prev = node.prev);
    this._cnt--;
    return node.value;
  }

  popleft() {
    const node = this.nil.next;
    if (node.value === "") return null;
    (node.next.prev = this.nil), (this.nil.next = node.next);
    this._cnt--;
    return node.value;
  }

  get length() {
    return this._cnt;
  }
  get front() {
    return this.nil.next.value;
  }
  get back() {
    return this.nil.prev.value;
  }
}
Main(require("fs").readFileSync(0, "utf8"));

Python solution:
from collections import deque
import sys

# from atcoder.fenwicktree import FenwickTree
# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.string import suffix_array,lcp_array,z_algorithm
# from atcoder.math import inv_mod,crt,floor_sum
# from atcoder.convolution import convolution,convolution_int
# from atcoder.modint import ModContext,Modint
# from atcoder.dsu import DSU
# from atcoder.maxflow import MFGraph
# from atcoder.mincostflow import MCFGraph
# from atcoder.scc import SCCGraph
# from atcoder.twosat import TwoSAT


def debug(*args, sep=" ", end="\n") -> None:
    print(*args, sep=sep, end=end, file=sys.stderr)


def main():
    global inf, MOD
    input = sys.stdin.read().split()
    ptr = 0
    inf = float("inf")
    MOD = 998244353

    N, K = map(int, input[ptr:ptr + 2]); ptr += 2
    if K == 1:
        print('Yes')
        sys.exit()
    NK = N * K
    G = [[] for _ in range(NK)]
    for _ in range(NK - 1):
        u, v = map(lambda x: int(x) - 1, input[ptr:ptr + 2]); ptr += 2
        G[u].append(v)
        G[v].append(u)
    q = deque([0])
    qq = []
    par = [-1] * NK
    while q:
        i = q.popleft()
        qq.append(i)
        for j in G[i]:
            if j != par[i]:
                par[j] = i
                q.append(j)
    w = [1] * NK
    c = [0] * NK
    for i in qq[::-1]:
        if (w[i] < K and c[i] > 1) or w[i] > K or (w[i] == K and c[i] > 2):
            print('No')
            sys.exit()
        if not w[i] == K:
            w[par[i]] += w[i]
            c[par[i]] += 1
    print('Yes')


if __name__ == "__main__":
    main()

Ruby solution:
(N, K), *UV = readlines.map{_1.split.map(&:to_i)}

g = Array.new(N*K){[]}
UV.each do |u, v|
  u, v = u - 1, v - 1
  g[u] << v
  g[v] << u
end
s = [[0, -1, 0]]
l = [1]*(N*K)
while (v, p, t = s.pop)
  if t == 0
    s << [v, p, 1]
    g[v].each{|u| s << [u, v, 0] if u != p}
  else
    c = 0
    g[v].each do |u|
      if u != p
        l[v] += l[u]
        c += 1 if l[u] > 0
      end
    end
    case
    when l[v] > K || c >= 3
      puts 'No'
      exit
    when l[v] < K && c >= 2
      puts 'No'
      exit
    when l[v] == K
      l[v] = 0
    end
  end
end
puts 'Yes'