Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Partition the Graph CodeChef Solution
Problem -Partition the Graph 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.
Partition the Graph CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
int timer, tin[N], c[N], bad, cnt[3];
vector <int> U, V, adj[N];
void dfs(int v, int pr, int color) {
tin[v] = ++timer;
c[v] = color;
++cnt[color];
if (timer & 1)
U.push_back(v);
else
V.push_back(v);
for (auto to : adj[v]) {
if (to != pr) {
if (c[to] == c[v])
bad = 1;
dfs(to, v, (color == 1 ? 2 : 1));
}
}
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
int g;
cin >>g;
while (g--) {
int n;
cin >> n;
timer = bad = cnt[1] = cnt[2] = 0;
U.clear(); V.clear();
for (int i = 1; i <= n; ++i)
adj[i].clear(), c[i] = tin[i] = 0;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, -1, 1);
if (!bad && cnt[1] == n /2) {
cout << 1 << '\n';
for (int i = 1; i <= n; ++i) {
if (c[i] == 1)
cout << i << ' ';
}cout<<endl;
for (int i = 1; i <= n; ++i) {
if (c[i] == 2)
cout << i<< ' ';
}
cout <<endl;
continue;
}
cout << 2 << '\n';
for (auto u : U)
cout<< u<< ' ';
cout << '\n';
for (auto v : V)
cout << v << ' ';
cout << '\n';
}
return 0;
}Partition the Graph CodeChef Solution in PYTH 3
# cook your dish here
import sys
sys.setrecursionlimit(10 ** 6)
def solve():
n = int(input())
adj = [[]for i in range(n + 1)]
temp = [[], []]
vec = []
for i in range(0, n - 1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
def dfs1(v, par, ct):
temp[ct].append(v)
for i in adj[v]:
if(i == par):
continue
dfs1(i, v, ct^1)
def dfs2(v, par):
vec.append(v)
for i in adj[v]:
if(i == par):
continue
dfs2(i, v)
dfs1(1, 0, 0)
if(len(temp[0]) == len(temp[1])):
print(1)
print(*temp[0])
print(*temp[1])
else:
print(2)
temp[0] = []
temp[1] = []
vec = []
dfs2(1, 0)
ct = 0
for i in vec:
temp[ct].append(i)
ct ^= 1
print(*temp[0])
print(*temp[1])
T = int(input())
for t in range(0, T):
solve()Partition the Graph CodeChef Solution in JAVA
import java.util.*;
import java.io.*;
public class Main {
static class Print {
private final BufferedWriter bw;
public Print() {
this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
}
public void print(Object object) throws IOException {
bw.append("" + object);
}
public void println(Object object) throws IOException {
print(object);
bw.append("\n");
}
public void close() throws IOException {
bw.close();
}
}
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
}
public static void main(String[] args) throws IOException {
Reader scn = new Reader();
Print p = new Print();
int t = scn.nextInt();
while (t-- > 0) {
int n = scn.nextInt();
ArrayList<Integer> neigh[] = new ArrayList[n + 1];
for (int i = 0; i < n; i++) {
neigh[i + 1] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
int a = scn.nextInt();
int b = scn.nextInt();
neigh[a].add(b);
neigh[b].add(a);
}
int[] k = new int[n + 1];
ArrayList<Integer> part[] = new ArrayList[2];
part[0] = new ArrayList<>(n / 2);
part[1] = new ArrayList<>(n / 2);
dfs(neigh, 1, k, part, 0);
// System.out.println(part[0]);
// System.out.println(part[1]);
if (part[0].size() == part[1].size()) {
p.println(1);
for (Integer i : part[0]) {
p.print(i + " ");
}
p.println("");
for (Integer i : part[1]) {
p.print(i + " ");
}
p.println("");
} else {
part[0] = new ArrayList<>(n / 2);
part[1] = new ArrayList<>(n / 2);
k = new int[n + 1];
dfs1(neigh, 1, k, part, 0);
p.println(2);
for (Integer i : part[0]) {
p.print(i + " ");
}
p.println("");
for (Integer i : part[1]) {
p.print(i + " ");
}
p.println("");
}
}
p.close();
}
private static void dfs1(ArrayList<Integer>[] neigh, int i, int[] k, ArrayList<Integer>[] part, int j) {
if (k[i] == 1) {
return;
}
if(j==0){
if (part[0].size() - part[1].size() == 1)
j=1;
}
if (j == 1) {
if (part[1].size() - part[0].size() == 1)
j=0;
}
k[i] = 1;
part[j].add(i);
if (j == 0) {
for (Integer a : neigh[i]) {
dfs1(neigh, a, k, part, 1);
}
} else {
for (Integer a : neigh[i]) {
dfs1(neigh, a, k, part, 0);
}
}
}
private static void dfs(ArrayList<Integer>[] neigh, int i, int[] k, ArrayList<Integer>[] part, int j) {
if (k[i] == 1) {
return;
}
k[i] = 1;
part[j].add(i);
if (j == 0) {
for (Integer a : neigh[i]) {
dfs(neigh, a, k, part, 1);
}
} else {
for (Integer a : neigh[i]) {
dfs(neigh, a, k, part, 0);
}
}
}
// public static void main(String[] args) throws IOException {
// Reader scn = new Reader();
// Print p = new Print();
// int t = scn.nextInt();
// while (t-- > 0) {
// int n = scn.nextInt();
// HashSet<Integer> map[] = new HashSet[n + 1];
//
// for (int i = 1; i <= n; i++) {
// map[i] = new HashSet<>();
// }
//
// for (int i = 0; i < n - 1; i++) {
// int a = scn.nextInt();
// int b = scn.nextInt();
// map[a].add(b);
// map[b].add(a);
// }
// HashSet<Integer> map1[] = new HashSet[2];
// map1[0] = new HashSet<>();
// map1[1] = new HashSet<>();
// int ans = dfs(map1, n, map);
// if(ans==1){
// p.println(1);
// for(Integer i:map1[0]){
// p.print(i+" ");
// }
// p.println("");
// for(Integer i:map1[1]){
// p.print(i+" ");
// }
// p.println("");
// }else{
// map1[0]=new HashSet<>();
// map1[1] = new HashSet<>();
//
// HashSet<Integer> map2[] = new HashSet[n+1];
//
// for (int i = 1; i <= n; i++) {
// map2[i] = new HashSet<>();
// }
//
// HashSet<Integer> k = new HashSet<>();
// dfs2(map,map2,1,n,0,0,k);
// for(int i=1;i<=n;i++){
// for(Integer a:map[i]){
// for(Integer b:map[i]){
// if(!map2[a].contains(b)&&a!=b){
// map2[a].add(b);
// map2[b].add(a);
// }
// }
// }
// }
//// for(int i=0;i<n;i++){
//// System.out.println(map[i+1]);
//// System.out.println(map2[i+1]);
//// }
// ans = dfs3(map1, n, map,map2);
//
// p.println(2);
// for(Integer i:map1[0]){
// p.print(i+" ");
// }
// p.println("");
// for(Integer i:map1[1]){
// p.print(i+" ");
// }
// p.println("");
// }
// }
// p.close();
// }
//
// private static int dfs3(HashSet<Integer>[] map1, int n,
// HashSet<Integer>[] map, HashSet<Integer>[] map2) {
// HashSet<Integer> k = new HashSet<>();
// for (int i = 1; i <= n; i++) {
// if (!k.contains(i))
// dfs4(i, map1, n, map, k, 0,map2);
// }
// if(map1[0].size()==map1[1].size()){
// return 1;
// }else{
// return 0;
// }
// }
//
// private static void dfs4(int i, HashSet<Integer>[] map1, int n,
// HashSet<Integer>[] map, HashSet<Integer> k, int j,
// HashSet<Integer>[] map2) {
// if (k.contains(i))
// return;
// if(j==0){
// if(map1[0].size()-map1[1].size()==1)
// return;
// }
//
// if(j==1){
// if(map1[1].size()-map1[0].size()==1)
// return;
// }
// k.add(i);
// map1[j].add(i);
// if (j == 0) {
// for (Integer a : map[i]) {
// dfs4(a, map1, n, map, k, 1, map2);
// }
// for (Integer a : map2[i]) {
// dfs4(a, map1, n, map, k, 1, map2);
// }
// } else {
// for (Integer a : map[i]) {
// dfs4(a, map1, n, map, k, 0, map2);
// }
//
// for (Integer a : map2[i]) {
// dfs4(a, map1, n, map, k, 0, map2);
// }
// }
//
// }
//
// private static void dfs2(HashSet<Integer>[] map, HashSet<Integer>[] map2,
// int i, int n, int p2, int p1, HashSet<Integer> k) {
// if(k.contains(i))
// return;
//
// if(p1!=0){
// map2[i].add(p1);
// map2[p1].add(i);
// }
//
// k.add(i);
// for (Integer a : map[i]) {
// dfs2(map, map2, a, n, i, p2, k);
// }
//
// }
//
// private static int dfs(HashSet<Integer>[] map1, int n, HashSet<Integer>[]
// map) {
// HashSet<Integer> k = new HashSet<>();
// for (int i = 1; i <= n; i++) {
// if (!k.contains(i))
// dfs1(i, map1, n, map, k, 0);
// }
// if(map1[0].size()==map1[1].size()){
// return 1;
// }else{
// return 0;
// }
// }
//
// private static void dfs1(int i, HashSet<Integer>[] map1, int n,
// HashSet<Integer>[] map, HashSet<Integer> k, int j) {
// if (k.contains(i))
// return;
//
// k.add(i);
// map1[j].add(i);
// if (j == 0) {
// for (Integer a : map[i]) {
// dfs1(a, map1, n, map, k, 1);
// }
// } else {
// for (Integer a : map[i]) {
// dfs1(a, map1, n, map, k, 0);
// }
// }
//
// }
//
}Partition the Graph CodeChef Solution in PYTH
from random import randint
import numpy as np
test = False
T = int(raw_input().strip())
for i in range(T):
N = int(raw_input().strip())
edges = []
neighbors = {}
for j in range(N - 1):
edge = map(int, raw_input().strip().split(" "))
edges.append(edge)
if test: print edge
if edge[0] in neighbors:
neighbors[edge[0]].append(edge[1])
else:
neighbors[edge[0]] = [edge[1]]
if edge[1] in neighbors:
neighbors[edge[1]].append(edge[0])
else:
neighbors[edge[1]] = [edge[0]]
visited = [False] * (N + 1)
visited[1] = True
currentVs = [1]
nextVs = neighbors[1]
evens = [1]
odds = []
# odds = neighbors[1]
evenLeaves = []
oddLeaves = []
even = True
while nextVs != []:
even = not even
currentVs = nextVs
nextVs = []
for v in currentVs:
if len(neighbors[v]) == 1:
if even:
evenLeaves.append(v)
else:
oddLeaves.append(v)
else:
if even:
evens.append(v)
else:
odds.append(v)
visited[v] = True
for neighbor in neighbors[v]:
if not visited[neighbor]:
nextVs.append(neighbor)
if test:
for v in neighbors:
print "v and neighbors = ", v, neighbors[v]
print "evens = ", evens
print "odds = ", odds
print "evenLeaves = ", evenLeaves
print "oddLeaves = ", oddLeaves
moves = (len(oddLeaves) + len(odds) - len(evenLeaves) - len(evens)) / 2
if moves != 0:
if test: print "moves = ", moves
print "2"
if moves > 0:
evenLeaves += oddLeaves[:moves]
oddLeaves = oddLeaves[moves:]
else:
oddLeaves += evenLeaves[:-moves]
evenLeaves = evenLeaves[-moves:]
else:
print "1"
evens += evenLeaves
odds += oddLeaves
print ' '.join(str(x) for x in evens)
print ' '.join(str(x) for x in odds)Partition the Graph 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 FactCache = 1000;
const int BIG = int.MaxValue >> 4;
List<int>[] g;
TreeGraph tree;
TreeDistances distances;
int n;
byte[] color;
#endregion
public void Solve()
{
int T = Ni();
for (int t = 1; t <= T; t++)
{
n = Ni();
color = new byte[n + 1];
g = ReadGraph(n);
int root = 1;
for (int i=1; i<=n; i++)
{
if (g[i].Count==1)
{
root = i;
break;
}
}
tree = new TreeGraph(g, root);
distances = new TreeDistances(tree, g);
int k = solveGraph();
WriteLine(k);
WriteLine(string.Join(" ", Enumerable.Range(1, n).Where(x => color[x] == 1)));
WriteLine(string.Join(" ", Enumerable.Range(1, n).Where(x => color[x] == 2)));
}
}
public int solveGraph()
{
int whitesNeeded = CheckBipartite();
if (whitesNeeded == 0)
return 1;
Array.Clear(color, 0, color.Length);
Blanket();
return 2;
}
bool Blanket()
{
int blacks = 0;
int whites = 0;
for (int iu = 0; iu < tree.TreeSize; iu++)
{
int u = tree.Trace[iu];
int c = color[u];
if (c == White)
whites++;
else if (c == Black)
blacks++;
}
if (blacks * 2 > tree.TreeSize
|| whites * 2 > tree.TreeSize)
return false;
int whitesNeeded = blacks - whites;
for (int iu = 0; iu < tree.TreeSize; iu++)
{
int u = tree.Trace[iu];
if (color[u] == 0)
{
if (whitesNeeded > 0)
{
color[u] = White;
whitesNeeded -= 1;
}
else
{
color[u] = Black;
whitesNeeded += 1;
}
}
}
return whitesNeeded == 0;
}
const int White = 1;
const int Black = 2;
#region Bipartite Matching
int[] mr;
int[] mc;
BitArray seen;
public bool BipartiteMatching(int k)
{
mr = new int[n+1];
mc = new int[n + 1];
for (int i = 1; i < mr.Length; i++)
mr[i] = -1;
for (int i = 1; i < mc.Length; i++)
mc[i] = -1;
seen = new BitArray(n + 1);
var ct = 0;
for (var i = 1; i <= n; i++)
{
seen.SetAll(false);
if (mr[i]>0 || FindMatch(i, mr, mc, k)) ct++;
}
return ct==n;
}
public int MaxDistance()
{
var ct = 1;
for (int i = 1; i <= n; i++)
{
ct = Math.Max(ct, tree.Distance(i, mr[i]));
}
return ct;
}
public bool FindMatch(int i, int[] mr, int[] mc, int k)
{
var queue = new Queue<Entry>();
queue.Enqueue(new Entry { P = -1, U = i, D=0 });
while (queue.Count > 0)
{
var e = queue.Dequeue();
var u = e.U;
var p = e.P;
var d = e.D;
foreach(var j in g[u])
{
if (j == p) continue;
if (d+1<=k)
queue.Enqueue(new Entry { P = u, U = j, D = d + 1 });
if (seen[j]) continue;
seen[j] = true;
if (mc[j] < 0 || FindMatch(mc[j], mr, mc, k))
{
mr[i] = j;
mc[j] = i;
mr[j] = i;
mc[i] = j;
color[i] = White;
color[j] = Black;
return true;
}
}
}
return false;
}
public struct Entry
{
public int U;
public int P;
public int D;
}
#endregion
#region Helpers
static int[] BreadFirst(TreeGraph tree, List<int>[] graph, int root)
{
int[] trace = new int[graph.Length];
trace[0] = root;
int pos = 0;
int limit = 1;
while (pos < limit)
{
int u = trace[pos++];
int p = tree.Parent[u];
foreach (var v in graph[u])
{
if (v == p) continue;
trace[limit++] = v;
}
}
Debug.Assert(tree.TreeSize == limit);
return trace;
}
public int CheckBipartite()
{
int black = 0;
int white = 0;
Array.Clear(color, 0, color.Length);
color[tree.Trace[0]] = Black;
for (int iu = 0; iu < tree.TreeSize; iu++)
{
int u = tree.Trace[iu];
int c = color[u];
if (c == Black) black++; else white++;
int p = tree.Parent[u];
foreach (int v in g[u])
{
if (v != p) color[v] = Flip(c);
}
}
return black - white;
}
byte Flip(int color)
{
if (color == White)
return Black;
else if (color == Black)
return White;
return (byte)color;
}
public static int GetDiameter(TreeGraph tree, List<int>[] g)
{
int[] height = new int[tree.Trace.Length + 1];
int maxPath = 0;
for (int iu = tree.TreeSize - 1; iu >= 0; iu--)
{
int u = tree.Trace[iu];
int p = tree.Parent[u];
int maxheight = 0;
int maxheight2 = 0;
foreach (int v in g[u])
{
if (v == p) continue;
int h = height[v] + 1;
if (h > maxheight2)
{
if (h > maxheight)
{
maxheight2 = maxheight;
maxheight = h;
}
else
{
maxheight2 = h;
}
}
}
int pathlength = maxheight + maxheight2;
maxPath = Max(maxPath, pathlength);
height[u] = maxheight + 1;
}
return maxPath;
}
public static int JumpSearch1Based(Func<int, bool> test, int n)
{
int left = 1;
int right = n;
while (left < right)
{
if (test(left) == false)
{
if (left * 2 < right)
{
left = left * 2;
}
else
{
left = left + 1;
break;
}
}
else
{
right = left - 1;
left = (left >> 1) + 1;
break;
}
}
return BinarySearch(test, left, right);
}
public static int JumpSearch(Func<int, bool> test, int left, int right)
{
return JumpSearch1Based(x => test(left + x - 1), right - left + 1);
}
public static int BinarySearch(Func<int, bool> test, int left, int right)
{
while (left <= right)
{
int mid = left + (right - left >> 1);
if (test(mid) == false)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
#endregion
#region Graph Construction
public static List<int>[] ReadGraph(int n, int m = -1)
{
var g = NewGraph(n);
if (m < 0)
m = n - 1;
for (int i = 0; i < m; i++)
{
int u = Ni();
int v = Ni();
g[u].Add(v);
g[v].Add(u);
}
return g;
}
public static List<int>[] NewGraph(int n)
{
var g = new List<int>[n + 1];
for (int i = 0; i <= n; i++)
g[i] = new List<int>();
return g;
}
#endregion
#region TreeGraph
public partial 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)
{
int* stack = stackalloc int[Graph.Length + 1];
int stackSize = 0, treeSize = 0;
stack[stackSize++] = r;
Parent[r] = -1;
while (stackSize > 0)
{
int u = stack[--stackSize];
Trace[treeSize++] = u;
Head[u] = u;
Sizes[u] = 1;
foreach (int 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--)
{
int u = Trace[iu];
int p = Parent[u];
var neighbors = Graph[u];
int maxSize = 0;
for (int i = 0; i < neighbors.Count; i++)
{
int 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)
{
int 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--)
{
int 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)
{
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)
{
int 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 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;
int 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);
public List<Segment> Query(int x, int y, bool edges = false)
{
// up segs in ascending order, down segs in descending order
segs.Clear();
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
{
segs.Add(new Segment(Begin[ry], Begin[y], -1));
y = Parent[ry];
ry = Head[y];
}
}
int lcaIndex = Min(Begin[x], Begin[y]);
int 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));
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
}
public class TreeDistances
{
public int[] MaxDist;
public int[] Height;
public int[] InverseHeight;
public TreeDistances(TreeGraph t, List<int>[] g)
{
int n = t.Trace.Length;
int treeSize = t.TreeSize;
int[] queue = t.Trace;
Height = new int[n + 1];
InverseHeight = new int[n + 1];
for (int iu = t.TreeSize; iu >= 0; iu--)
{
int u = t.Trace[iu];
int ht = -1;
int p = t.Parent[u];
foreach (int v in g[u])
{
if (v == p) continue;
ht = Math.Max(Height[v], ht);
}
Height[u] = 1 + ht;
}
MaxDist = new int[n + 1];
for (int iu = 0; iu < treeSize; iu++)
{
int u = queue[iu];
int max = InverseHeight[u], max2 = int.MinValue;
int p = t.Parent[u];
foreach (int v in g[u])
{
if (v != p)
{
int h = 1 + Height[v];
if (h > max2)
{
max2 = h;
if (max2 > max)
Swap(ref max, ref max2);
}
}
}
foreach (int v in g[u])
{
if (v != p)
{
int h = 1 + Height[v];
int h2 = h != max ? max : max2;
InverseHeight[v] = 1 + h2;
}
}
MaxDist[u] = Math.Max(InverseHeight[u], Height[u]);
}
}
}
#endregion
#region Library
#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 long IntPow(long n, long p)
{
long b = n;
long result = 1;
while (p != 0)
{
if ((p & 1) != 0)
result = (result * b);
p >>= 1;
b = (b * b);
}
return result;
}
public 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)
{
ulong 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)
{
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()
{
int c = SkipSpaces();
bool neg = c == DASH;
if (neg) { c = Read(); }
long number = c - ZERO;
while (true)
{
int 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)
{
char[] list = new char[n];
for (int i = 0, c = SkipSpaces(); i < n; i++, c = Read()) list[i] = (char)c;
return list;
}
static string Ns()
{
int 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 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;
string 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);
int line = new StackTrace(e, true).GetFrames()
.Select(x => x.GetFileLineNumber()).FirstOrDefault(x => x != 0);
int 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
}Partition the Graph CodeChef Solution Review:
In our experience, we suggest you solve this Partition the Graph 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 Partition the Graph CodeChef Solution.
Conclusion:
I hope this Partition the Graph 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!
