考场并不知道动态dp这东西。
考虑$f[i][0]$表示$i$这个位置必须不选
$f[i][1]$表示$i$这个位置必须选
显然可以每次$O(n)$来重新dp一次。
但是我们发现，每次的要求只修改两个位置到LCA的$f$值和$LCA$到根的$f$值。
考虑每次用矩阵转移，将矩阵弄在边上，将矩阵重载为$min和+$
然后修改一个点就是一个点到根的路径上的矩阵合并起来，用倍增维护。
然后同时到LCA的时候不好处理，讨论一下就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define M 100010 4 #define LL long long 5 #define inf 1000000000000ll 6 inline int read() { 7 char ch = getchar(); int x = 0, f = 1; 8 while(ch < '0' || ch > '9') { 9 if(ch == '-') f = -1; 10 ch = getchar(); 11 } 12 while('0' <= ch && ch <= '9') { 13 x = x * 10 + ch - '0'; 14 ch = getchar(); 15 } 16 return x * f; 17 } 18 int p[M]; 19 struct Edge{ 20 int u, v, Next; 21 } G[M * 2]; 22 int head[M], tot; 23 inline void add(int u, int v) { 24 G[++ tot] = (Edge){u, v, head[u]}; 25 head[u] = tot; 26 } 27 struct Node{ 28 LL a[2][2]; 29 Node() { 30 a[0][1] = a[1][0] = a[1][1] = a[0][0] = inf; 31 } 32 inline Node operator * (const Node& rhs) const { 33 Node ret; 34 for(int i = 0; i <= 1; ++ i) { 35 for(int j = 0; j <= 1; ++ j) { 36 for(int k = 0; k <= 1; ++ k) { 37 ret.a[i][j] = min(ret.a[i][j], a[i][k] + rhs.a[k][j]); 38 } 39 } 40 } 41 return ret; 42 } 43 inline void print() { 44 printf("%lld %lld ", a[0][0], a[0][1]); 45 printf("%lld %lld ", a[1][0], a[1][1]); 46 } 47 } g[M][19]; 48 LL f[M][2]; 49 int h[M], ft[M][19]; 50 inline void dfs(int x, int fa) { 51 h[x] = h[fa] + 1; 52 ft[x][0] = fa; 53 for(int i = 1; i <= 18; ++ i) { 54 ft[x][i] = ft[ft[x][i - 1]][i - 1]; 55 } 56 f[x][1] = p[x]; 57 for(int i = head[x]; i != -1; i = G[i].Next) { 58 if(G[i].v == fa) continue; 59 dfs(G[i].v, x); 60 f[x][0] += f[G[i].v][1]; 61 f[x][1] += min(f[G[i].v][0], f[G[i].v][1]); 62 } 63 } 64 inline void dfs1(int x, int fa) { 65 for(int i = head[x]; i != -1; i = G[i].Next) { 66 if(G[i].v == fa) continue; 67 dfs1(G[i].v, x); 68 g[G[i].v][0].a[0][0] = inf; 69 g[G[i].v][0].a[1][0] = f[x][0] - f[G[i].v][1]; 70 g[G[i].v][0].a[0][1] = f[x][1] - min(f[G[i].v][0], f[G[i].v][1]); 71 g[G[i].v][0].a[1][1] = f[x][1] - min(f[G[i].v][0], f[G[i].v][1]); 72 } 73 } 74 inline int lca(int x, int y) { 75 if(h[x] < h[y]) swap(x, y); 76 int t = h[x] - h[y]; 77 for(int i = 0; i <= 18; ++ i) { 78 if((1 << i) & t) { 79 x = ft[x][i]; 80 } 81 } 82 if(x == y) return x; 83 for(int i = 18; i >= 0; -- i) { 84 if(ft[x][i] != ft[y][i]) { 85 x = ft[x][i]; 86 y = ft[y][i]; 87 } 88 } 89 return ft[x][0]; 90 } 91 int main() { 92 int n = read(), m = read(); 93 char s[10]; scanf("%s", s); 94 for(int i = 1; i <= n; ++ i) { 95 p[i] = read(); 96 } 97 memset(head, -1, sizeof(head)); 98 for(int i = 1; i < n; ++ i) { 99 int u = read(), v = read(); 100 add(u, v), add(v, u); 101 } 102 dfs(1, 0); 103 dfs1(1, 0); 104 for(int i = 1; i <= 18; ++ i) { 105 for(int j = 1; j <= n; ++ j) { 106 if(ft[j][i] != 0) { 107 g[j][i] = g[j][i - 1] * g[ft[j][i - 1]][i - 1]; 108 } 109 } 110 } 111 while(m --) { 112 int x = read(), a = read(), y = read(), b = read(); 113 if(h[x] < h[y]) { 114 swap(x, y), swap(a, b); 115 } 116 int LCA = lca(x, y); 117 Node A, B; 118 A.a[0][a] = f[x][a]; 119 B.a[0][b] = f[y][b]; 120 for(int i = 18; i >= 0; -- i) { 121 if(h[ft[x][i]] > h[LCA]) { 122 A = A * g[x][i]; 123 x = ft[x][i]; 124 } 125 } 126 for(int i = 18; i >= 0; -- i) { 127 if(h[ft[y][i]] > h[LCA]) { 128 B = B * g[y][i]; 129 y = ft[y][i]; 130 } 131 } 132 133 if(y == LCA) { 134 A = A * g[x][0]; 135 A.a[0][b ^ 1] = inf; 136 } 137 else { 138 Node C; 139 C.a[0][0] = f[LCA][0] - f[x][1] - f[y][1] + A.a[0][1] + B.a[0][1]; 140 C.a[0][1] = f[LCA][1] - min(f[x][0], f[x][1]) - min(f[y][0], f[y][1]); 141 C.a[0][1] += min(A.a[0][0], A.a[0][1]) + min(B.a[0][0], B.a[0][1]); 142 A = C; 143 } 144 x = ft[x][0]; 145 for(int i = 18; i >= 0; -- i) { 146 if(h[ft[x][i]] >= 1) { 147 A = A * g[x][i]; 148 x = ft[x][i]; 149 } 150 } 151 if(A.a[0][0] == inf && A.a[0][1] == inf) { 152 puts("-1"); 153 } 154 else printf("%lld ", min(A.a[0][0], A.a[0][1])); 155 } 156 }