USACO/mootube.java at master · jonathanshi568/USACO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
ID: jshi
LANG: JAVA
TASK: mootube
 */
import java.io.*;
import java.util.*;
class node{
	public int index;
	public long[][] connections;
	public int c;

	public node(int index) {
		this.index = index;
		c=0;
		connections = new long[100][2];
	}

	public int getC() {
		return c;
	}

	public void incC() {
		c+=1;
	}
}

class mootube {

	public static int method(long rel, long vid, node[] nodes, long prevVid) {
		int result = 0 ;
		node n = nodes[(int) vid];
		for(int i = 0; i<n.getC(); i++) {
			if(n.connections[i][0]==prevVid) {
				continue;
			}
			if(n.connections[i][1]>=rel) {
				result=result+1+method(rel, n.connections[i][0], nodes, vid);
			}
			else {
				continue;
			}
		}
		return result;
	}

	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(new File("mootube.in"));
		PrintWriter pw = new PrintWriter(new File("mootube.out"));

		int videos = sc.nextInt();
		long rules = sc.nextInt();
		node[] nodes = new node[videos];
		for(int i = 0; i<videos; i++) {
			nodes[i]=new node(i);
		}
		for(int i = 0; i<videos-1; i++) {
			int index1 = sc.nextInt()-1;
			int index2 = sc.nextInt()-1;
			long relevance = sc.nextInt();
			nodes[index1].connections[nodes[index1].getC()][0]=index2;
			nodes[index1].connections[nodes[index1].getC()][1]=relevance;
			nodes[index2].connections[nodes[index2].getC()][0]=index1;
			nodes[index2].connections[nodes[index2].getC()][1]=relevance;
			nodes[index1].incC();
			nodes[index2].incC();
		}

		for(int i = 0; i<rules; i++) {
			long rel = sc.nextInt();
			long vid = sc.nextInt();
			pw.print(method(rel, vid-1, nodes, -1));
			if(i!=rules-1) {
				pw.println();
			}

		}
		pw.close();

	}

}