洛谷 U140313 暗影已逝
洛谷傳送門
題目背景
“光與影輪回不止”
題目描述
然而逃跑并不能阻止蟲群的襲擊。大主教決定吸引更多異蟲來到夏古拉斯,在所有星靈撤離後,前往神廟,通過裡面的機關來引爆這顆星球,以此重創異蟲。
神廟記載着星靈的曆史——光明聖堂武士和黑暗聖堂武士的抗争史。
機關的形狀為一顆無根樹。已知每個節點初始沒有屬性,大主教可用自己的靈能為這些節點添上一種屬性(屬性僅有兩種,黑暗和光明,分别用0和1表示),而每一個葉子節點i都有一個觸發屬性Ci。Ci定義為從根節點到i上的簡單路徑上最後一個帶有屬性的節點的屬性(也可以是i本身)。隻有每個Ci都符合條件時,機關才可觸發。
蟲群已包圍神廟,大主教需要在最短的時間内觸發機關,于是他找到了你——JDOI滴神。他想知道最少添加幾次屬性能觸發機關。
輸入格式
第一行兩個整數,N,M。分别表示節點的個數和葉子節點的個數。
第二行M個整數,表示Ci。
接下來N-1行,每行2個整數x,y。表示x到y有一條邊相連。
輸出格式
一個整數,表示最少操作數。
題解:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e6+6;
int n,m;
int opt[maxn],cnt[2];
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1];
int dp[maxn][2];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int f)
{
if(x<=m)
{
if(opt[x])
dp[x][0]=1;
else
dp[x][1]=1;
return;
}
int tmp0=0,tmp1=0;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs(y,x);
tmp0+=dp[y][0];
tmp1+=dp[y][1];
}
dp[x][0]=min(tmp0,tmp1+1);
dp[x][1]=min(tmp0+1,tmp1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d",&opt[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs(m+1,0);
int tmp0=0,tmp1=0;
int x=m+1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
tmp0+=dp[y][0];
tmp1+=dp[y][1];
}
int ans=min(tmp0,tmp1);
printf("%d\n",ans+1);
return 0;
}