###### tags: `apcs` `歷屆練習` `解題筆記` `自主學習`
樹狀圖結構題型練習
===
[TOC]
{%hackmd BJrTq20hE %}
## 樹狀圖結構
由於時間有限。來不及學習困難的演算法，這裡用較耗時的物件導向方式模擬樹狀圖。創一個類別儲存節點，有值、高度、父節點、一個ArrayList存放子結點
:::info
不是最佳解法，比較耗時，是比較好理解的作法
:::
```java=
class E{
//值、高度
int value,layers;
//父結點
E parent;
E(int value,int layers){
this.layers = layers;
this.value = value;
}
//子結點
ArrayList<E> children = new ArrayList<>();
}
```
## 高度計算
輸入後將葉結點獨立出來運算，每個葉結點都往上跑持續，如果父結點大於爺結點+1就不更新，最後就達成所有層數都是最大的。
```java=
for(int i = 0;i < leaf.size();i++) {
int x = leaf.get(i);
int now = tree.get(x).value;
while(true){
if(tree.get(now).parent == null)
break;
//沒超過就不加
if(tree.get(now).parent.layers <tree.get(now).layers+1) {
tree.get(now).parent.layers =tree.get(now).layers+1;
}
//跳下一個
now = tree.get(now).parent.value;
}
}
```
## [APCS歷屆:樹狀圖分析]([https:/](https://zerojudge.tw/ShowProblem?problemid=c463)/)
把高度算完後加總高度
```java=
import java.io.*;
import java.util.*;
public class zj_c463 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<E> tree = new ArrayList<>();
//建立結點
for(int i = 0;i <= n;i++) {
tree.add(new E(i,0));
}
//建立樹的關係
for(int i = 1;i <= n;i++) {
String[] d = br.readLine().split(" ");
int t = Integer.parseInt(d[0]);
if(t > 0)
tree.get(i).layers = -1;
for(int j = 1;j <= t;j++) {
int c = Integer.parseInt(d[j]);
tree.get(i).children.add(tree.get(c));
tree.get(c).parent = tree.get(i);
}
}
//葉結點獨立出來
ArrayList<Integer>leaf = new ArrayList<>();
int root = 0;
for(int i = 1;i <= n;i++) {
if(tree.get(i).parent == null)
root = i;
if(tree.get(i).layers == 0)
leaf.add(tree.get(i).value);
}
//把葉結點跑一次更新
for(int i = 0;i < leaf.size();i++) {
int x = leaf.get(i);
int now = tree.get(x).value;
while(true){
if(tree.get(now).parent == null)
break;
if(tree.get(now).parent.layers <tree.get(now).layers+1) {
tree.get(now).parent.layers =tree.get(now).layers+1;
}
//跳下一個
now = tree.get(now).parent.value;
}
}
long ans = 0;
for(int i = 1;i <= n;i++) {
ans+=tree.get(i).layers;
}
System.out.println(root);
System.out.println(ans);
}
}
class E{
//值、高度
int value,layers;
//父結點
E parent;
E(int value,int layers){
this.layers = layers;
this.value = value;
}
//子結點
ArrayList<E> children = new ArrayList<>();
}
```
## [APCS歷屆:血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
第四子題有點超時
建立高度後，每個節點跑一次，一個子結點:最佳親緣關係為子結點高度+1；兩個以上:高度最高的兩個子結點高度相加再+2，找最大值
```java=
import java.io.BufferedReader;
import static java.lang.Integer.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class zj_b967 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = "";
while((s = br.readLine()) != null) {
//輸入
int n = parseInt(s);
ArrayList<E> list = new ArrayList<>();
//建立0到n-1的節點(值,層數(預設0),父節點(預設null))
for(int i = 0;i < n;i++) {
list.add(new E(i,0));
}
//建立關係
for(int i = 0;i < n-1;i++) {
String[] d = br.readLine().split(" ");
int a = parseInt(d[0]);
int b = parseInt(d[1]);
list.get(b).parent = list.get(a);
list.get(a).children.add(list.get(b));
//將不是葉節點的節點標記
list.get(a).layers = -1;
}
//紀錄葉節點的編號
ArrayList<Integer> temp = new ArrayList<>();
for(int i = 0;i < n;i++) {
if(list.get(i).layers == 0) {
temp.add(i);
}
}
//把每個葉節點往上跑直到頂(parent=null)刷新每個節點的層數大小
for(int i = 0;i < temp.size();i++) {
int x = temp.get(i);
int now = list.get(x).value;
while(true) {
//到頂就結束
if(list.get(now).parent == null) {
break;
}
//刷新層數大小
if(list.get(now).parent.layers <list.get(now).layers+1) {
list.get(now).parent.layers =list.get(now).layers+1;
}
//跳下一個
now = list.get(now).parent.value;
}
}
int ans = 0;
for(int i = 0;i < n;i++) {
//如果子節點數量為1，長度為子節點層數+1
//如果子節點數量大於2，長度為最大層數的兩個子節點+2
int x = 0;
int size = list.get(i).children.size();
if(size == 1) {
x = list.get(i).children.get(0).layers+1;
}else if(size >= 2) {
int[] tmp = new int[size];
for(int j = 0;j < size;j++) {
tmp[j] = list.get(i).children.get(j).layers;
}
Arrays.sort(tmp);
x = tmp[size-1] + tmp[size-2] + 2;
}
//只取最大值所以超過再刷新
if(x > ans)
ans = x;
}
System.out.println(ans);
}
}
}
//建立一個有值、層數、父節點的class,用arrayList存子節點
class E{
int value,layers;
E parent;
E(int value,int layers){
this.layers = layers;
this.value = value;
}
ArrayList<E> children = new ArrayList<>();
}
```
## APCS歷屆:貨物分配
這裡用陣列儲存二元線段樹，判斷左右重量運算，可惜最後三個側資MLE沒有拿滿
```java=
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class zj_f163 {
public static int cl = 0,cr = 1,p = 2,weight = 3,n,m,hasBeenCounted = 4;
//cl左子結，cr右子結，p父結，weight重量
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//輸入
String[] d = br.readLine().split(" ");
n = Integer.parseInt(d[0]);
m = Integer.parseInt(d[1]);
int[] w = new int[m];
int[][] tree = new int[n*2][5];
//輸入原始重量
d = br.readLine().split(" ");
for(int i = 0;i <n;i++) {
tree[i+n][weight] = Integer.parseInt(d[i]);
}
//輸入要計算的東西
d = br.readLine().split(" ");
for(int i = 0;i < m;i++)
w[i] = Integer.parseInt(d[i]);
//建立二元樹
for(int i = 0;i <n-1;i++) {
d = br.readLine().split(" ");
int a = Integer.parseInt(d[0]);
int b = Integer.parseInt(d[1]);
int c = Integer.parseInt(d[2]);
tree[a][cl] = b;
tree[a][cr] = c;
tree[b][p] = a;
tree[c][p] = a;
}
//計算節點重量
count(tree,1);
//判斷
for(int i :w) {
int place = 1;
while(true) {
//左子結重量小於或等於右子結重量:place變左
if(tree[tree[place][cl]][weight] <= tree[tree[place][cr]][weight])
place = tree[place][cl];
//右小於左，place變右
else
place = tree[place][cr];
//結點重量加入
tree[place][weight] += i;
//place超過分裝站範圍退出
if(place>= n)
break;
}
System.out.print(place+" ");
}
}
//計算結點重量
public static void count(int[][] t,int x) {
if(x>= n)
return;
count(t,t[x][cl]);
count(t,t[x][cr]);
t[x][weight] = t[t[x][cl]][weight]+t[t[x][cr]][weight];
}
}
```
Sign in with Wallet
Connect another wallet