結果
問題 | No.364 門松木 |
ユーザー |
|
提出日時 | 2016-06-11 01:49:47 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,398 bytes |
コンパイル時間 | 2,362 ms |
コンパイル使用メモリ | 83,596 KB |
実行使用メモリ | 364,004 KB |
最終ジャッジ日時 | 2024-10-09 12:44:43 |
合計ジャッジ時間 | 30,800 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 1 RE * 24 |
ソースコード
package yukicoder;import java.util.ArrayList;import java.util.Scanner;public class Main{public static void main(String[] args) {new Main().solve();}ArrayList<Integer>[] edges = new ArrayList[50000];int[] A;// dp[v][A[u]]:頂点vの子頂点uをvにつないだ時の門松列の総数int[][] dp = new int[1000][50000];int[] num_up = new int[1000];// num_up[v]:頂点vの持つ数字より大きい数を持つ子頂点の数int[] num_down = new int[1000];// num_up[v]:頂点vの持つ数字より小さい数を持つ子頂点の数int[] sc_down = new int[1000];// sc_up[v]:頂点vの子頂点がvより小さくなるような場合に含める最大の門松列の総数int[] sc_up = new int[1000];// sc_down[v]:頂点vの子頂点がvより大きくなるな場合に含める最大の門松列の総数int dfs(int cur, int pre) {int ret = 0;for (int i = 0; i < edges[cur].size(); i++) {int u = edges[cur].get(i);if (pre != u) {ret = Math.max(ret, dfs(u, cur));if (A[cur] > A[u]) {if (dp[u][A[cur]] >= 0) {dp[cur][A[u]] = Math.max(sc_up[u] - dp[u][A[cur]], dp[cur][A[u]]);} else {dp[cur][A[u]] = Math.max(num_up[u] + sc_up[u], dp[cur][A[u]]);}} else if (A[cur] < A[u]) {if (dp[u][A[cur]] >= 0) {dp[cur][A[cur]] = Math.max(sc_down[u] - dp[u][A[cur]], dp[cur][A[cur]]);} else {dp[cur][A[u]] = Math.max(num_down[u] + sc_down[u], dp[cur][A[u]]);}}}}for (int i = 0; i < 1000; i++) {if (dp[cur][i] >= 0) {if (A[cur] > i) {num_down[cur]++;sc_down[cur] += dp[cur][i];} else if (A[cur] < i) {num_up[cur]++;sc_up[cur] += dp[cur][i];}}}sc_down[cur] += num_down[cur] * (num_down[cur] - 1) / 2;sc_up[cur] += num_up[cur] * (num_up[cur] - 1) / 2;return Math.max(ret, Math.max(sc_down[cur], sc_up[cur]));}int N;void solve() {Scanner sc = new Scanner(System.in);N = sc.nextInt();A = new int[N];for (int i = 0; i < 50000; i++)edges[i] = new ArrayList<>();for (int i = 0; i < 1000; i++)for (int j = 0; j < 50000; j++)dp[i][j] = -1;for (int i = 0; i < N; i++)A[i] = sc.nextInt();for (int i = 0; i < N - 1; i++) {int x = sc.nextInt() - 1;int y = sc.nextInt() - 1;edges[x].add(y);edges[y].add(x);}int ret = dfs(0, -1);System.out.println(ret);}}