题目描述
这题太虎了，所以没有背景。
给你一棵树，边有黑白两种颜色，你每次可以选择两个点，把这两个点之间的唯一简单路径上的所有边颜色取反，某些边要求最终颜色必须是黑色，还有些边没有要求，问最少操作多少次能达到目的
输入格式
第一行一个整数 \(n\)，代表点数
接下来\(n-1\)行，每行三个数\(x,y,z\)，代表点 \(i\) 与点 \(x\) 之间有一条边，若 \(y\) 为 \(0\) 代表初始为白色，否则为黑色，若\(z\)为\(0\)代表不对最终颜色做要求，否则代表要求为黑色。
输出格式
达到目的的最少操作多少次数
样例
样例输入
7
1 0 1
1 1 1
2 0 1
2 0 1
3 1 1
3 0 1
样例输出
3
数据范围与提示
对于 \(30\%\) 的数据，所有\(x\)等于\(1\)
对于另外 \(30\%\) 的数据，所有边最终都必须为黑色
对于 \(100\%\) 的数据，\(n \leq 1000000\)
分析
树上的贪心
如果儿子中有偶数个节点不符合条件，直接两两配对
否则将剩下的节点能上传就上传
代码
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e6+5;
int n,h[maxn],tot=1;
struct asd{
int to,nxt,val;
}b[maxn];
void ad(int aa,int bb,int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int ans;
int dfs(int now,int fa){
rg int cnt=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa) continue;
rg int haha=dfs(u,now);
if(b[i].val==1){
cnt++;
} else if(haha){
if(b[i].val==-1) cnt++;
else ans++;
}
}
ans+=cnt/2;
if(cnt&1) return 1;
else return 0;
}
int main(){
memset(h,-1,sizeof(h));
n=read();
rg int aa,bb,cc;
for(rg int i=2;i<=n;i++){
aa=read(),bb=read(),cc=read();
if(cc==0){
ad(i,aa,-1);
ad(aa,i,-1);
} else {
if(bb==0){
ad(i,aa,1);
ad(aa,i,1);
} else {
ad(i,aa,0);
ad(aa,i,0);
}
}
}
ans+=dfs(1,0);
printf("%d\n",ans);
return 0;
}
