问题 G: 夜刀与黑角
如果两个人全部访问则 ans = 4*（n-1）
考虑删除没有遍历的节点
对于角色A:
1.对于以u为根的节点，如果存在A需要访问的节点，则u必须要访问
2.对于以u为根的节点，如果存在B需要访问的节点x,dep[x]-dep[u]>=D,则u须要访问
3.其他情况，可以不用访问
dfs求每个节点是否需要访问，如果不需要则-2（一来一回）
点击查看代码
const int N=2e5+10;
vector<int> g[200010];
int n,D,ans;
//d1[u],A角色以u为根节点要到达的最远距离（深度）
int k1[N],k2[N],d[N],d1[N],d2[N];
void dfs(int u,int fa){
//标记访问深度
if(k1[u]) d1[u]=d[u];
if(k2[u]) d2[u]=d[u];
for(int v:g[u]){
if(v==fa) continue;
d[v]=d[u]+1;
dfs(v,u);
d1[u]=max(d1[u],d1[v]);
d2[u]=max(d2[u],d2[v]);
}
if(u==1) return;
//以u为根的子树A角色不用访问，则不用访问
if(!d1[u]&&d2[u]-d[u]<D) ans-=2;//来回-2
//同理
if(!d2[u]&&d1[u]-d[u]<D) ans-=2;
}
void bu_f(){
n=read(),D=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
g[x].push_back(y);
g[y].push_back(x);
}
//假设全部点都要遍历
ans=4*(n-1);
int m1=read();
for(int i=1;i<=m1;i++){
int x=read();
k1[x]=1;
}
int m2=read();
for(int i=1;i<=m2;i++){
int x=read();
k2[x]=1;
}
d[1]=1;
//删掉不用遍历的点
dfs(1,0);
write(ans);
}
考虑d[i]到d[i+1]天转移要么是k+1,要么是d[i+1]-d[i],两则取最小即可
点击查看代码
LL a[100010];
LL ans,n,k;
void bu_f(){
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
ans=k+1;
for(int i=2;i<=n;i++) {
ans+=min(k+1,a[i]-a[i-1]);
}
cout<<ans;
}