题解 (by;zjvarphi)
树形 (dp) 题目
有一个结论:对于一个图,有多少奇度数的点,处以二就是答案,奇度数指的是和它相连的边中被反转的是奇数
证明很好证
那么设 (dp_{i,0}) 表示当没翻转 (i->fa_i) 的边时在 (i) 的子树中有多少奇度数点, (dp_{i,1}) 表示翻转了
那么分情况转移,设 (w1) 表示和 (i) 相连的且在它子树中的边被翻转奇数条时子树中除去 (i) 的答案,此时,若不算和父亲相连的边,这个点就是一个奇度数点
[dp_{i,0}=w1+1\
dp_{i,1}=w1
]
那么 (w2) 就代表偶数
[dp_{i,0}=w2\
dp_{i,1}=w2+1
]
每次需要判断 (i->fa) 的类型,然后必须转移的就不能更新 (dp_{i,0}),不能转移的同理
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define node(x,y) (node){x,y}
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=1e5+7,INF=1e9+7;
int first[N],t=1,n;
struct edge{int v,nxt,w;}e[N<<1];
inline void add(int u,int v,int w) {e[t].v=v,e[t].w=w,e[t].nxt=first[u],first[u]=t++;}
struct node{int w1,w2;}dp[N][2];
inline int operator>(const node &n1,const node &n2) {return n1.w1==n2.w1?n1.w2>n2.w2:n1.w1>n2.w1;}
inline node operator+(const node &n1,const node &n2) {return node(n1.w1+n2.w1,n1.w2+n2.w2);}
void dfs(int x,int fa,int w) {
node tmp1=node(INF,INF);
node tmp2=node(0,0);
for (ri i(first[x]),v;i;i=e[i].nxt) {
if ((v=e[i].v)!=fa) {
dfs(v,x,e[i].w);
node fg1=cmin(tmp1+dp[v][0],tmp2+dp[v][1]);
node fg2=cmin(tmp2+dp[v][0],tmp1+dp[v][1]);
tmp1=fg1,tmp2=fg2;
}
if (w==1) dp[x][0]=node(INF,INF);
else dp[x][0]=cmin(node(tmp1.w1+1,tmp1.w2),tmp2);
if (!w) dp[x][1]=node(INF,INF);
else dp[x][1]=cmin(node(tmp1.w1,tmp1.w2+1),node(tmp2.w1+1,tmp2.w2+1));
}
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n);
for (ri i(1),u,v,c,w;i<n;p(i)) {
read(u),read(v),read(c),read(w);
if (w==2) add(u,v,w),add(v,u,w);
else add(u,v,c!=w),add(v,u,c!=w);
}
dfs(1,0,2);
printf("%d %d
",dp[1][0].w1>>1,dp[1][0].w2);
return 0;
}
}
int main() {return nanfeng::main();}