NOIp2018
一道DP难度正常的题。
做这道题前最好先看看【模板】最小树形图
。
题目传送门
学会此题需要掌握的知识：
- LCA倍增
- 动态规划
- 数据结构部分（例如：链，vector）
题目大意
有个城市，可以花
p[i] 代价把i 点驻扎，要求任2个相邻点至少有1个被驻扎。给出m 组询问，每次强制两个点的状态（驻扎或者不驻扎），求出每次的最少花费的money 。
简要分析
暴力 只能拿不到50%得分（这远远不够）。
首先不难看出题目要我们求的是最小覆盖（任意一条边至少有一个点被选中）。
此题目有多种解法（参考本文首篇题解）：
-
最小权覆盖集 = 全集 - 最大权独立集
-
倍增（本人用的）
-
每条链中间的 DP 转移全部相同，因而我们可以批量地对所有需要进行这一转移的 DP 进行转移，从而加快速度。
时间复杂度都是： O( n log n) 。
树形DP就是在树形结构里使用动态规划。
DP算是一种暴力算法，直接做当然会超时。
这就需要 LCA倍增 来优化。而倍增要解决的问题是每次询问一条链的 dp 值。 我们要把每个节点拿或者不拿的子树的最小权值算出来，才可在根上算出答案。
这道题目我们首先考虑什么情况是非法的。很明显，只有两个相邻的节点被强制要求不驻兵时，才会出现非法的情况。
题目很容易超时，所以我们要尽量降低时间复杂度还要制定那两个点的状态。
DP+倍增 是最好的解题方案。(本人认为)
将dp转移写成矩阵后发现它可以非常方便地支持合并，那么我们现在的问题就变成了维护树上连续一段的这些矩阵的乘积。可以直接树剖，但由于我们对点权没有直接修改，所以可以直接考虑倍增。
主要是思维复杂，代码都还可以。
AC代码：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;//万能头文件: #include<bits/stdc++.h>
const long long infinity = 100000000000000000ll;//肯定够大了
const int MaxN=100000;
vector<int> g[MaxN+1];
long long dp[MaxN+1][2], f[MaxN+1][20][2][2];
int cost[MaxN+1], pre[MaxN+1][20], depth[MaxN+1];
void getDP(int x){//树形DP
dp[x][1] = cost[x];
for(int j=0; j+1<20; ++j){
if(not pre[x][j])
break; /* pre[x,j]=x的1<<j级祖先 */
pre[x][j+1] = pre[pre[x][j]][j];
}
for(int i=0, len=g[x].size(); i<len; ++i){//普通DP模板
if(g[x][i] == pre[x][0])
continue;
depth[g[x][i]] = depth[x]+1;
pre[g[x][i]][0] = x;
getDP(g[x][i]);
dp[x][0] += dp[g[x][i]][1]; /* 普通的树形DP */
dp[x][1] += min(dp[g[x][i]][0],dp[g[x][i]][1]);
}
}
void getF(int x){
if(pre[x][0]){ // x != 1
f[x][0][0][1] = f[x][0][1][1] = dp[pre[x][0]][1]-min(dp[x][0],dp[x][1]);
f[x][0][1][0] = dp[pre[x][0]][0] - dp[x][1];
/* 做减法是去掉自己这个子树的贡献 */
f[x][0][0][0] = infinity; // invalid
}
for(int j=1; j<20; ++j){
if(not pre[x][j])
break;
for(int X=0; X<2; ++X)
for(int F=0; F<2; ++F){ /* 状态转移 */
f[x][j][X][F] = infinity;
for(int mid=0; mid<2; ++mid) /* 枚举中间点状态 */
f[x][j][X][F] = min(f[x][j][X][F],f[x][j-1][X][mid]+f[pre[x][j-1]][j-1][mid][F]);
}
}
for(int i=0, len=g[x].size(); i<len; ++i)
if(g[x][i] != pre[x][0])
getF(g[x][i]);
}
void goUp(int a,int j,long long &a0,long long &a1){
long long t0 = a0, t1 = a1; /* 向上跳跃，顺便更新 */
a0 = min(t0+f[a][j][0][0],t1+f[a][j][1][0]);
a1 = min(t0+f[a][j][0][1],t1+f[a][j][1][1]);
}
long long solve(int a,int x,int b,int y){
if(depth[a] < depth[b]){
swap(a,b); swap(x,y);
}
long long a0, a1, b0, b1, l0, l1;
a0 = a1 = b0 = b1 = l0 = l1 = infinity;
if(x == 0) a0 = dp[a][0];
if(x == 1) a1 = dp[a][1];
if(y == 0) b0 = dp[b][0];
if(y == 1) b1 = dp[b][1];
/* 没有被赋值就非法，infinity */
for(int i=19; ~i; --i)
if((depth[a]-depth[b])>>i&1){
goUp(a,i,a0,a1);
a = pre[a][i];
}
int lca; /* 先倍增到lca，求得lca上的值 */
if(a == b){
lca = a;
if(y == 0) l0 = a0;
if(y == 1) l1 = a1;
}
else{
for(int i=19; ~i; --i)
if(pre[a][i] != pre[b][i]){
goUp(a,i,a0,a1); goUp(b,i,b0,b1);
a = pre[a][i]; b = pre[b][i];
}
lca = pre[a][0];
l0 = dp[lca][0]-dp[a][1]-dp[b][1]+a1+b1;
l1 = dp[lca][1]-min(dp[a][0],dp[a][1])-min(dp[b][0],dp[b][1])+min(a0,a1)+min(b0,b1);
/* 同样的，减掉原有的贡献，加上新的贡献 */
}
for(int i=19; ~i; --i)
if(depth[lca]>>i&1){
goUp(lca,i,l0,l1);
lca = pre[lca][i];
}
if(min(l0,l1) < infinity)
return min(l0,l1);
return -1; // invalid（一个大的数，请看上面）
/*如果函数执行不需要返回计算结果，也经常需要返回一个状态码来表示函数执行的顺利与否（-1,1和0就是最常用的状态码），主调函数可以通过返回值判断被调函数的执行情况。(来自百度)
}
int main(){//下面就没有什么难度啦,只是调用函数。
int n, m; // 然而TPYE并没有什么用
scanf("%d %d %*[^\n]",&n,&m);
for(int i=1; i<=n; ++i)
scanf("%d",&cost[i]);
for(int i=1,a,b; i<n; ++i){
scanf("%d %d",&a,&b);
g[b].push_back(a);
}
g[a].push_back(b);
getDP(1), getF(1);
for(int a,x,b,y; m; --m){
scanf("%d %d %d %d",&a,&x,&b,&y);
/*比 cin 效率快得多，避免超时。*/
printf("%lld\n",solve(a,x,b,y));
/*比 cout 效率快得多，避免超时。*/
}
return 0;//完美结束
}本人首篇题解，qwq。
感谢观看。