欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#树形DP# [ssloj 1469] W

程序员文章站 2022-06-29 13:31:47
...

Title

#树形DP# [ssloj 1469] W


Solution

转载于:https://www.cnblogs.com/butterflydew/p/9776076.html
#树形DP# [ssloj 1469] W


Code

#include<cstdio> 
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std; 
const int inf=1e9; 
const int N=1e5+10; 
struct node{
	int y,z,next; 
}a[N<<1];
int tot,head[N]; 
int n; 
struct nodd{
	int x,y; 
	nodd friend operator +(nodd x,nodd y){
		nodd q=(nodd){x.x+y.x,x.y+y.y}; 
		return q; 
	}
	bool friend operator <(nodd x,nodd y){
		return (x.x==y.x)?(x.y<y.y):(x.x<y.x); 
	}
}d[N][2];
void add(int x,int y,int z){
	a[++tot]=(node){y,z,head[x]}; head[x]=tot; 
}
nodd mymin(nodd x,nodd y){return x<y?x:y;} 
void dfs(int x,int fa,int flag){
	nodd w1=(nodd){inf,inf},w2=(nodd){0,0},n1,n2; 
	for(int i=head[x];i;i=a[i].next){
		int y=a[i].y;  
		if (y==fa) continue; 
		dfs(y,x,a[i].z); 
		n1=mymin(d[y][0]+w1,d[y][1]+w2); 
		n2=mymin(d[y][1]+w1,d[y][0]+w2); 
		w1=n1,w2=n2; 
	}
	if (flag==1||flag==2) d[x][1]=mymin((nodd){w1.x,w1.y+1},(nodd){w2.x+1,w2.y+1}); 
		else d[x][1]=(nodd){inf,inf}; 
	if (flag==0||flag==2) d[x][0]=mymin((nodd){w1.x+1,w1.y},w2); 
		else d[x][0]=(nodd){inf,inf}; 
}
int main(){
	int size = 256 << 20; 
    char*p=(char*)malloc(size) + size;
    __asm__("movl %0, %%esp\n" :: "r"(p) );

	scanf("%d",&n); 
	rep(i,2,n){
		int x,y,c,f; 
		scanf("%d%d%d%d",&x,&y,&c,&f); 
		c=((f==2)?f:(c!=f)); 
		add(x,y,c); add(y,x,c); 
	}
	dfs(1,0,2); 
	printf("%d %d",d[1][0].x>>1,d[1][0].y); 
	return 0; 
}