M u v 将u所在的堆移动到v所在的堆的上面
C u 求u的下面有多少块
带权并查集
import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { public static void main(String[] args){ new Task().solve() ; } } class Task{ final int N = 30000 ; int[] size = new int[N+8] ; int[] high = new int[N+8] ; int[] father = new int[N+8] ; void init(){ for(int i = 1 ; i <= N ; i++){ father[i] = i ; size[i] = 1 ; high[i] = 0 ; } } int getFather(int u){ if(father[u] == u) return u ; int fu = father[u] ; int root = getFather(fu) ; high[u] += high[fu] ; return father[u] = root ; } void merge(int from , int to){ int rootFrom = getFather(from) ; int rootTo = getFather(to) ; high[rootTo] = size[rootFrom] ; size[rootFrom] += size[rootTo] ; father[rootTo] = father[rootFrom] ; } void solve(){ init() ; int p = in.nextInt() ; while(p-- > 0){ if("M".equals(in.next())){ int from = in.nextInt() ; int to = in.nextInt() ; merge(from, to) ; } else{ int u = in.nextInt() ; int root = getFather(u) ; out.println(size[root] - high[u] - 1) ; } } out.flush() ; } InputReader in = new InputReader(System.in) ; PrintWriter out = new PrintWriter(System.out) ; } class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } }