1 条题解
-
1
#include<bits/stdc++.h> using namespace std; #define M 100010 #define LL long long #define inf 1000000000000ll inline int read() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int p[M]; struct Edge{ int u, v, Next; } G[M * 2]; int head[M], tot; inline void add(int u, int v) { G[++ tot] = (Edge){u, v, head[u]}; head[u] = tot; } struct Node{ LL a[2][2]; Node() { a[0][1] = a[1][0] = a[1][1] = a[0][0] = inf; } inline Node operator * (const Node& rhs) const { Node ret; for(int i = 0; i <= 1; ++ i) { for(int j = 0; j <= 1; ++ j) { for(int k = 0; k <= 1; ++ k) { ret.a[i][j] = min(ret.a[i][j], a[i][k] + rhs.a[k][j]); } } } return ret; } inline void print() { printf("%lld %lld\n", a[0][0], a[0][1]); printf("%lld %lld\n", a[1][0], a[1][1]); } } g[M][19]; LL f[M][2]; int h[M], ft[M][19]; inline void dfs(int x, int fa) { h[x] = h[fa] + 1; ft[x][0] = fa; for(int i = 1; i <= 18; ++ i) { ft[x][i] = ft[ft[x][i - 1]][i - 1]; } f[x][1] = p[x]; for(int i = head[x]; i != -1; i = G[i].Next) { if(G[i].v == fa) continue; dfs(G[i].v, x); f[x][0] += f[G[i].v][1]; f[x][1] += min(f[G[i].v][0], f[G[i].v][1]); } } inline void dfs1(int x, int fa) { for(int i = head[x]; i != -1; i = G[i].Next) { if(G[i].v == fa) continue; dfs1(G[i].v, x); g[G[i].v][0].a[0][0] = inf; g[G[i].v][0].a[1][0] = f[x][0] - f[G[i].v][1]; g[G[i].v][0].a[0][1] = f[x][1] - min(f[G[i].v][0], f[G[i].v][1]); g[G[i].v][0].a[1][1] = f[x][1] - min(f[G[i].v][0], f[G[i].v][1]); } } inline int lca(int x, int y) { if(h[x] < h[y]) swap(x, y); int t = h[x] - h[y]; for(int i = 0; i <= 18; ++ i) { if((1 << i) & t) { x = ft[x][i]; } } if(x == y) return x; for(int i = 18; i >= 0; -- i) { if(ft[x][i] != ft[y][i]) { x = ft[x][i]; y = ft[y][i]; } } return ft[x][0]; } int main() { int n = read(), m = read(); char s[10]; scanf("%s", s); for(int i = 1; i <= n; ++ i) { p[i] = read(); } memset(head, -1, sizeof(head)); for(int i = 1; i < n; ++ i) { int u = read(), v = read(); add(u, v), add(v, u); } dfs(1, 0); dfs1(1, 0); for(int i = 1; i <= 18; ++ i) { for(int j = 1; j <= n; ++ j) { if(ft[j][i] != 0) { g[j][i] = g[j][i - 1] * g[ft[j][i - 1]][i - 1]; } } } while(m --) { int x = read(), a = read(), y = read(), b = read(); if(h[x] < h[y]) { swap(x, y), swap(a, b); } int LCA = lca(x, y); Node A, B; A.a[0][a] = f[x][a]; B.a[0][b] = f[y][b]; for(int i = 18; i >= 0; -- i) { if(h[ft[x][i]] > h[LCA]) { A = A * g[x][i]; x = ft[x][i]; } } for(int i = 18; i >= 0; -- i) { if(h[ft[y][i]] > h[LCA]) { B = B * g[y][i]; y = ft[y][i]; } } if(y == LCA) { A = A * g[x][0]; A.a[0][b ^ 1] = inf; } else { Node C; C.a[0][0] = f[LCA][0] - f[x][1] - f[y][1] + A.a[0][1] + B.a[0][1]; C.a[0][1] = f[LCA][1] - min(f[x][0], f[x][1]) - min(f[y][0], f[y][1]); C.a[0][1] += min(A.a[0][0], A.a[0][1]) + min(B.a[0][0], B.a[0][1]); A = C; } x = ft[x][0]; for(int i = 18; i >= 0; -- i) { if(h[ft[x][i]] >= 1) { A = A * g[x][i]; x = ft[x][i]; } } if(A.a[0][0] == inf && A.a[0][1] == inf) { puts("-1"); } else printf("%lld\n", min(A.a[0][0], A.a[0][1])); } }
- 1
信息
- ID
- 83
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 4
- 上传者