Scout Guard
Time complexity:\(O(nd)\)
The previous compilation
First of all, when I did it,\(f\)Indicates downward\(j\)layer,\(g\)It's up and down together
Transfer\(f_{u,j}=f_{v,j-1}\)
But this is obviously not right
This is because I didn't think about something clearly:
-
The difference between key points and ordinary points
-
A large part of the coverage will overlap, and other points will not be considered.
Look at the second point first
For other things, you only need to consider the son's father's
Why?
Because the son treats his son's and the father's son's treatment is very easy, he only needs not to accumulate during the transfer but to take\(\min\)
Then there is something for ancestors, so you can't be simple -1
Yes, so add one dimension\(j\)Indicates how many layers are covered upward
The father does not need to cover the points that the son has covered for his father, and this needs to be deducted in the state
So set\(g_{u,j}\)express\(g\)down\(j-1\)Is the layer covered?\(j\)Minimum cost for all layers and below to be covered
Regarding the first point, we can not cover ordinary points
Transform, if the points covered by this point are all ordinary points, then it will have no effect whether this point covers or not. This question is about the cost. We will directly eliminate its cost, that is,\(f_{u,0}=g_{u,0}=0\)
However, he can transfer to 0, but if he wants to use it to cover other points, his expenses must be calculated, so\(f_{u,j}=val_u\) \(,j \leq d\)
List all the situations when you want to transfer
-
I cover me, my son is covered by me
-
I'm covered by my son
Everything is ready! Jiangdong arson ball! putarrowTransfer!
\(f_{u,i}=\min(f_{u,i}+g_{v,i},g_{u,i+1}+f_{v,i+1})\)
The first one is easy to understand, the second one is\(u\)To cover up\(i\)layer,\(v\)It must be covered upward\(i+1\)layer, and\(v\)Cover one layer upward and then fold it downwards\(i\)layer, so\(u\)of\(g\)Want to arrive\(i+1\)
Note that this is actually\(g\)All need to take one\(\sum\)but when transferring\(f_{u,i}\)The update is equivalent to picking up\(\sum\)
Therefore, the transfer must be updated first\(f\)Update again\(g\)of
The code is very historical
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
const int inf=9e18;
int n,d,val[N],head[N<<1],cnt;
bool vis[N];
struct node{int to,nxt;}e[N<<1];
void add(int u,int v){
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
}
int f[N][22],g[N][22];
void dfs(int u,int fa){
if(vis[u])f[u][0]=g[u][0]=val[u];
else f[u][0]=g[u][0]=0;
for(int i=1;i<=d;i++)f[u][i]=val[u];
f[u][d+1]=inf;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
for(int j=d;j>=0;j--)f[u][j]=min(f[u][j]+g[v][j],f[v][j+1]+g[u][j+1]);
for(int j=d;j>=0;j--)f[u][j]=min(f[u][j],f[u][j+1]);
g[u][0]=f[u][0];
for(int j=1;j<=d;j++)g[u][j]+=g[v][j-1];
for(int j=1;j<=d;j++)g[u][j]=min(g[u][j],g[u][j-1]);
}
}
signed main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>val[i];
}
int m;
cin>>m;
for(int i=1;i<=m;i++){
int x;
cin>>x;
vis[x]=1;
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
dfs(1,0);
cout<<f[1][0];
return 0;
}