关注
第二题是这样吗:#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int MAXN=1e5 + 5;
vector<int>edges[MAXN];
string color;
int dp[MAXN][2];
int vis[MAXN];
void add(int u,int v){
edges[u].push_back(v);
edges[v].push_back(u);
}
void dfs(int u){
dp[u][0]=0;
dp[u][1]=1;
vis[u]=1;
for(auto& v:edges[u]){
if(vis[v]==1)continue;
vis[v]=1;
dfs(v);
vis[v]=0;
if(color[v] == color[u]){
dp[u][0]+=min(dp[v][0]+1,dp[v][1]);
dp[u][1]+=min(dp[v][1],dp[v][0])+1;
}else {
dp[u][0]+=min(dp[v][0],dp[v][1]+1);
dp[u][1]+=min(dp[v][1],dp[v][0]+1);
}
}
}
int main(){
int n;cin>>n;
cin>>color;
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
add(a-1,b-1);
}
dfs(0);
cout<<min(dp[0][0],dp[0][1])<<endl;
return 0;
}
查看原帖
2 评论
相关推荐
点赞 评论 收藏
分享
等闲_:感觉咱们双非的同学都有一个共性,想证明双非也是能进大厂的,我之前所有的标签都喜欢带着双非,仿佛这样可以像别人证明自己的实力,现在我却不再想证明双非到底能不能进大厂,我的生活的所有者是我自己,享受生活,接受结果 点赞 评论 收藏
分享
2025-12-23 12:11
湖北理工学院 前端工程师 点赞 评论 收藏
分享
查看8道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客吐槽大会 #
12536次浏览 201人参与
# 软开人,秋招你打算投哪些公司呢 #
177626次浏览 1339人参与
# 帆软软件工作体验 #
10970次浏览 53人参与
# 实习,不懂就问 #
158060次浏览 1382人参与
# 运营人求职交流聚集地 #
208455次浏览 1091人参与
# 硬件人秋招进展 #
269291次浏览 3982人参与
# 国企秋招,你投了吗? #
58482次浏览 373人参与
# 毕业后不工作的日子里我在做什么 #
232661次浏览 1690人参与
# 关于春招你都做了哪些准备? #
125758次浏览 717人参与
# 快手工作体验 #
301667次浏览 2904人参与
# AI求职实录 #
18642次浏览 433人参与
# 硬件/芯片公司工作体验 #
146700次浏览 958人参与
# 今年春招是金一银二嘛? #
31573次浏览 293人参与
# 没关系,至少我的__很曼妙 #
13586次浏览 231人参与
# 1月小结:你过的开心吗? #
5779次浏览 132人参与
# 你的第一家实习公司是什么档次? #
14502次浏览 181人参与
# 抛开难度不谈,你最想去哪家公司? #
17974次浏览 246人参与
# 快手年终开大包 #
4339次浏览 58人参与
# 为什么有人零实习也能进大厂? #
17138次浏览 281人参与
# Prompt分享 #
19631次浏览 473人参与

