#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 6000 + 10;
int n;
int f[N][2], p[N]; // f[i][0]不选第i个员工的最大值 f[i][1]选第i个员工的最大值
int at[N];
vector<int> v[N];
// p[i]存第i名员工的直接上司 v[i]存第i名员工的下属
void init() {
for (int i = 1; i <= n; i ++ ) {
v[i].clear();
f[i][0] = f[i][1] = 0;
p[i] = -1;
}
for (int i = 1; i <= n; i ++ )
f[i][1] = at[i];
}
void dfs(int cur) {
for (int i = 0; i < v[cur].size(); i ++ ) {
int son = v[cur][i];
dfs(son);
f[cur][0] += max(f[son][1], f[son][0]);
f[cur][1] += f[son][0];
}
}
int main() {
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; i ++ )
scanf("%d", &at[i]);
init();
int a, b;
while (~scanf("%d%d", &a, &b)) {
if (a == 0 && b == 0)
break;
v[b].push_back(a);
p[a] = b;
}
int t = 1; // dfs起点
while (p[t] != -1)
t = p[t]; // 找老大
dfs(t);
printf("%d\n", max(f[t][1], f[t][0]));
}
return 0;
}
/*
求一个树中所有节点能到达的最远距离。要用两个dfs。
第一个dfs求出所有每个节点i在其子树中的正向最大距离和正向次大距离dist[i][0]和dist[i][1](如果i节点在子树中最大距离经过了2号儿子,那么次大距离就是不经过2号儿子的最大距离)。并且还要标记longest[i]=j表示节点i在其子树中的最大距离经过了节点j(即j是i的一个儿子)。
i节点的最远距离只有两种选择:i节点所在子树的最大距离,或者i节点连接它的父节点所能到达的最大距离。(即前者往下走,后者先往上走之后很可能也往下走)
dist[i][2]求法:i节点往它的父节j点走,如果它的父节点的正向最大距离不经过i的话,那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向最大距离+ W[i][j].
如果它的父节点的正向最大距离经过i的话,那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向次大距离+ W[i][j].
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int h[N], e[N * 10], ne[N * 10], idx, w[N * 10];
int dist[N][3];//dist[i][0,1,2]分别为正向最大距离,正向次大距离,反向最大距离
int longest[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs1(int u, int fa) { //第一个dfs求出所有每个节点i在其子树中的正向最大距离和正向次大距离和dist[i][0]和dist[i][1]
if (dist[u][0] >= 0)
return dist[u][0];
dist[u][0] = dist[u][1] = dist[u][2] = longest[u] = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
if (dist[u][0] < dfs1(j, u) + w[i]) {
longest[u] = j;
dist[u][1] = max(dist[u][1], dist[u][0]);
dist[u][0] = dfs1(j, u) + w[i];
} else if ( dist[u][1] < dfs1(j, u) + w[i])
dist[u][1] = max(dist[u][1], dfs1(j, u) + w[i]);
}
return dist[u][0];
}
void dfs2(int u, int fa) {
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
if (j == longest[u])
dist[j][2] = max(dist[u][2], dist[u][1]) + w[i];
else
dist[j][2] = max(dist[u][2], dist[u][0]) + w[i];
dfs2(j, u);
}
}
int main() {
while (~scanf("%d", &n)) {
memset(dist, -1, sizeof dist);
memset(h, -1, sizeof h);
memset(longest, -1, sizeof longest);
idx = 0;
for (int i = 2; i <= n; i ++ ) {
int a, b;
scanf("%d%d", &a, &b);
add(i, a, b);
add(a, i, b);
}
dfs1(1, -1);
dfs2(1, -1);
for (int i = 1; i <= n; i++)
printf("%d\n", max(dist[i][0], dist[i][2]));
}
return 0;
}
/*
就是每个子树的根节点(包括叶子节点)记录dp[i][0]与dp[i][1],前一个表示不包含根的最大值,后一个表示包含根的最大值。
那么我们可以得到对于dp[i][0],必然是所有分支中dp[child][0]与dp[child][1]中大于0的最大值的累加(因为不包含树根,所
以在根节点上的连通性不用保证),dp[i][1]必然是所有分支中dp[child][1]中大于0的最大值的累加再加上该树根本身的值(因为
要保证连通性)。最后只要比较dp[start][0]与dp[start][1],输出较大的一个即可。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N], e[N * 10], ne[N * 10], idx;
int x[N], y[N], w[N];
int f[N][2];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa) {
f[u][1] = w[u];
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
dfs(j, u);
f[u][0] = max(f[u][0], max(f[j][0], f[j][1]));
if (f[j][1] > 0)
f[u][1] += f[j][1];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d%d%d", &x[i], &y[i], &w[i]);
memset(h, -1, sizeof h);
idx = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j < i; j ++ )
if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1)
add(i, j), add(j, i);
for (int i = 1; i <= n; i ++ )
f[i][0] = 0;
dfs(1, -1);
printf("%d\n", max(f[1][0], f[1][1]));
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 10;
int longest[N];
int dist[N][3];
int f[N];
int n, m;
int h[N], e[N * 10], ne[N * 10], w[N * 10], idx;
int st_max[N][25], st_min[N][25], Log[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs1(int u, int fa) {
if (dist[u][0] >= 0)
return dist[u][0];
dist[u][0] = dist[u][1] = dist[u][2] = longest[u] = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
if (dist[u][0] < dfs1(j, u) + w[i]) {
dist[u][1] = dist[u][0];
longest[u] = j;
dist[u][0] = dfs1(j, u) + w[i];
} else if (dist[u][1] < dfs1(j, u) + w[i])
dist[u][1] = dfs1(j, u) + w[i];
}
return dist[u][0];
}
void dfs2(int u, int fa) {
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa)
continue;
if (j == longest[u])
dist[j][2] = max(dist[u][2], dist[u][1]) + w[i];
else
dist[j][2] = max(dist[u][2], dist[u][0]) + w[i];
dfs2(j, u);
}
}
void init() {
Log[1] = 0;
for (int i = 2; i <= n + 1; i ++ )
Log[i] = Log[i / 2] + 1;
for (int i = 1; i <= n; i ++ ) {
st_max[i][0] = f[i];
st_min[i][0] = f[i];
}
for (int j = 1; (1 << j) <= n; j ++ )
for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) {
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
}
}
int ask(int l, int r) {
int k = Log[r - l + 1];
return max(st_max[l][k], st_max[r - (1 << k) + 1][k]) - min(st_min[l][k], st_min[r - (1 << k) + 1][k]);
}
void solve(int q) {
int l = 1, r = 1;
int ans = 1;
while (l <= n && r <= n) {
while (r <= n && ask(l, r) <= q)
r ++ ;
ans = max(ans, r - l);
l ++ ;
}
printf("%d\n", ans);
}
int main() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
memset(h, -1, sizeof h);
idx = 0;
memset(dist, -1, sizeof dist);
for (int i = 1; i < n; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dfs1(1, -1);
dfs2(1, -1);
for (int i = 1; i <= n; i ++ )
f[i] = max(dist[i][0], dist[i][2]);
init();
while (m -- ) {
int q;
scanf("%d", &q);
solve(q);
}
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e3 + 10, INF = 0x3f3f3f3f;
typedef long long LL;
int n, m, Q;
LL ans;
int g[N][N];
int f[N][N];
bool st[N];
int dist[N];
vector<int> v[N];
int p[N];
void prim(int x) {
ans = 0LL;
for (int i = 0; i < n; i ++ )
dist[i] = g[x][i], p[i] = x, st[i] = false, v[i].clear();
st[0] = true, p[0] = -1, dist[0] = INF;
for (int i = 1; i < n; i ++ ) {
int t = 0;
for (int j = 0; j < n; j ++ ) {
if (!st[j] && dist[t] > dist[j])
t = j;
}
st[t] = true;
if (p[t] != -1) {
v[t].push_back(p[t]);
v[p[t]].push_back(t);
}
ans += (LL)dist[t];
for (int j = 0; j < n; j ++ ) {
if (!st[j] && dist[j] > g[t][j]) {
dist[j] = g[t][j];
p[j] = t;
}
}
}
}
int dfs(int u, int fa, int root) {
int res = INF;
for (int i = 0; i < v[u].size(); i ++ ) {
int j = v[u][i];
if (j == fa)
continue;
int temp = dfs(j, u, root);
res = min(res, temp);
f[u][j] = f[j][u] = min(f[u][j], temp);
}
if (root != fa)
res = min(res, g[root][u]);
return res;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
memset(g, 0x3f, sizeof g);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= m; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
prim(0);
for (int i = 0; i < n; i ++ )
dfs(i, -1, i);
LL sum = 0LL;
scanf("%d", &Q);
for (int i = 1; i <= Q; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (p[a] != b && p[b] != a)
sum += ans;
else
sum += (ans - g[a][b] + min(c, f[a][b]));
}
printf("%.4lf\n", 1.0 * sum / Q);
}
return 0;
}