| 103 | } |
| 104 | |
| 105 | public static boolean check(int u, int limit) { |
| 106 | preVal[0] = 0; |
| 107 | preNode[0] = u; |
| 108 | preLen = 0; |
| 109 | for (int k = 1; k <= cnte; k++) { |
| 110 | int v = to[edgeArr[k][0]]; |
| 111 | int w = weight[edgeArr[k][0]]; |
| 112 | for (int i = 1; i <= siz[v]; i++) { |
| 113 | curVal[i] = -INF; |
| 114 | } |
| 115 | curLen = 0; |
| 116 | dfs(v, u, 1, w >= limit ? 1 : -1, limit); |
| 117 | int ql = 1, qr = 0; |
| 118 | // 根据之前的信息，初步建立窗口，子树按秩处理非常重要 |
| 119 | for (int i = Math.min(preLen, limitr); i >= limitl; i--) { |
| 120 | while (ql <= qr && preVal[que[qr]] <= preVal[i]) { |
| 121 | qr--; |
| 122 | } |
| 123 | que[++qr] = i; |
| 124 | } |
| 125 | int down = limitr, up = limitl; |
| 126 | for (int i = 1; i <= curLen; i++) { |
| 127 | up--; |
| 128 | if (up >= 0 && up <= preLen) { |
| 129 | while (ql <= qr && preVal[que[qr]] <= preVal[up]) { |
| 130 | qr--; |
| 131 | } |
| 132 | que[++qr] = up; |
| 133 | } |
| 134 | if (ql <= qr && que[ql] == down) { |
| 135 | ql++; |
| 136 | } |
| 137 | down--; |
| 138 | if (ql <= qr && preVal[que[ql]] + curVal[i] >= 0) { |
| 139 | if (limit > ans) { |
| 140 | ans = limit; |
| 141 | ansu = curNode[i]; |
| 142 | ansv = preNode[que[ql]]; |
| 143 | } |
| 144 | return true; |
| 145 | } |
| 146 | } |
| 147 | for (int i = 1; i <= curLen; i++) { |
| 148 | if (i > preLen || curVal[i] > preVal[i]) { |
| 149 | preVal[i] = curVal[i]; |
| 150 | preNode[i] = curNode[i]; |
| 151 | } |
| 152 | } |
| 153 | preLen = Math.max(preLen, curLen); |
| 154 | } |
| 155 | return false; |
| 156 | } |
| 157 | |
| 158 | public static void calc(int u) { |
| 159 | getSize(u, 0); |