| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 283533 | ijxjdjd | Network (BOI15_net) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
package Tasks;
import Code.IO.InputReader;
import Code.Tree.DefaultTree;
import java.io.*;
import java.util.ArrayList;
import java.util.Set;
import java.util.Stack;
public class Network {
int[][] adj;
public void solve(int testNumber, InputReader in, PrintWriter out) {
try {
Reader r = new Reader();
int N = r.nextInt();
adj = new int[N][];
int[] from = new int[N-1];
int[] to = new int[N-1];
for (int i = 0; i < N - 1; i++) {
int a = r.nextInt() - 1;
int b = r.nextInt() - 1;
from[i] = a;
to[i] = b;
}
adj = DefaultTree.packU(N, from, to);
if (N == 2) {
out.println("1\n1 2");
} else {
for (int i = 0; i < N; i++) {
if (adj[i].length > 1) {
Set f = dfs(i);
if (f.a2 == -1) {
ans.add(new Set(f.a1, i));
} else {
ans.add(new Set(f.a1, f.a2));
}
break;
}
}
out.println(ans.size());
for (Set s : ans) {
out.println((s.a1 + 1) + " " + (s.a2 + 1));
}
}
}
catch (IOException e) {
}
}
ArrayList<Set> ans = new ArrayList<>();
Set dfs(int n) {
Stack<State> stack = new Stack<>();
stack.add(new State(n, n));
while (stack.size() > 0) {
State next = stack.peek();
int a = next.getNext();
if (a == -1) {
stack.pop();
if (stack.isEmpty()) {
return next.s;
}
if (next.cur == 1) {
stack.peek().merge(new Set(next.n));
}
else {
stack.peek().merge(next.s);
}
}
else {
stack.add(new State(a, next.n));
}
}
return null;
}
class State {
int cur;
int n;
int p;
Set s = null;
State(int n, int p) {
cur = 0;
this.n = n;
this.p = p;
}
int getNext() {
if (cur >= adj[n].length) {
return -1;
} else if (adj[n][cur] == p) {
cur++;
return getNext();
}
else {
return adj[n][cur++];
}
}
void merge(Set s) {
if (this.s == null) {
this.s = s;
}
else {
this.s.merge(s);
}
}
}
class Set {
int a1;
int a2;
void merge(Set s) {
if (s.a2 == -1 && this.a2 == -1) {
this.a2 = s.a1;
}
else if (s.a2 == -1){
ans.add(new Set(s.a1, this.a2));
this.a2 = -1;
}
else if (this.a2 == -1){
ans.add(new Set(this.a1, s.a2));
this.a1 = s.a1;
}
else {
ans.add(new Set(this.a1, s.a1));
this.a1 = this.a2;
this.a2 = s.a2;
}
}
Set(int a) {
this.a1 = a;
this.a2 = -1;
}
Set(int a, int b) {
this.a1 = a;
this.a2 = b;
}
}
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++];
}
}
}