雅礼 noip2018 模拟赛 day3 T3

典型树形dp

这里，我们应该看到一些基本性质：

①：如果这个边不能改（不是没有必要改），我们就不改，因为就算改过去还要改回来，显然不是最优的

注意：“不能改”是指边的性质和要求的相同而不包括对边的颜色没有要求的情况！

②：如果我们每翻转一条边，就认为将这条边的两个端点度数+1，那么不难看到，最后翻转的所有边构成的路径总数就是度数为奇数点个数的1/2

（性质②的证明：一条路径只会对两端的点产生度数上的影响，而中间的点都是+2，还是偶数，所以无影响）

接下来，我们进行dp：

记状态f[i][0/1]代表以i为根节点的子树，0/1代表根节点与父亲的边是否翻转

那么我们可以看到，这个dp包含两部分内容，一部分要保证路径数最少，另一部分要保证在满足路径数最小的前提下路径总长度最小，所以我们需要同时更新这两个值，这样用pair就是一个比较好的选择

接下来我们考虑更新：

在更新时我们使用两个参量：p和q，作为更新dp的中间步骤，用p代表不以i为端点做链，q代表以i为端点做链，设i的某个子节点为to，于是有：

$p=min(add(p,dp[to][0]),add(q,dp[to][1]))$

$q=min(add(p,dp[to][1]),add(q,dp[to][0]))$

其中p初始化为（0,0），q初始化为（INF，INF）

解释一下：这里pair的add就是对应元素相加（手写！非内置！）

而min操作表示先按pair第一关键字比较，再按第二关键字比较

那么这一步就是一个合并的过程：

首先，i不作为链的端点：分两类来合并：如果子节点与i的边翻转了，那么就要累在以i为端点的链里（因为i与父亲的边不翻转，那么i就将是个端点），如果子节点与i的边没有翻转，那么仅针对这棵子树而言，i并没有作为路径的端点，所以更新没有以i为端点链的代价

如果i作为链的端点，同样分两类来合并：如果子节点与i的边翻转了，那么i显然可以成为链的端点，前提是在此之前i并不是链的端点，所以用之前i不是链的端点的代价来更新；反之，如果子节点与i的边没有翻转，那么就此而言i并不是端点，可要求i是链的一个端点，这样就必须用i原先就是链的端点的代价来更新

遍历根节点所有子节点后，更新dp：

如果i与父亲的边没有翻转。即状态dp[i][0]：

首先，i不作为链的端点肯定是一种可能性，直接比较

接着，如果i是链的一个端点，i和父节点的边还没有翻转，那么说明在这个状态下i是真正的奇度点，所以将状态q的first+1后更新

如果i与父亲的边翻转了，同样分两类更新：

首先，i本身作为了链的端点，而由于i本身就是奇度点，所以仅需将q.second+1来更新即可

还有，如果i本身在下面并没有作为链的端点，而i却与父节点的边发生了翻转，所以i就成为了新的奇度点，同时链长还增加了，所以p.first,p.second均增加即可

最后答案即为dp[1][0].first/2,dp[1][0].second

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
  int next;
  int to;
  int val;
}edge[200005];
int head[100005];
int cnt=1;
pair <int,int> dp[100005][2];
int n;
void init()
{
  memset(head,-1,sizeof(head));
  cnt=1;
}
void add(int l,int r,int w)
{
  edge[cnt].next=head[l];
  edge[cnt].to=r;
  edge[cnt].val=w;
  head[l]=cnt++;
}
pair<int,int> addp(pair<int,int> a,pair<int,int> b)
{
	return make_pair(a.first+b.first,a.second+b.second);
}
void dfs(int x,int fx,int typ)
{
	pair <int,int> p,q;
	p=make_pair(0,0);
	q=make_pair(INF,INF);
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==fx)
		{
			continue;
		}
		dfs(to,x,edge[i].val);
		pair <int,int> temp1,temp2;
		temp1=min(addp(p,dp[to][0]),addp(q,dp[to][1]));
		temp2=min(addp(p,dp[to][1]),addp(q,dp[to][0]));
		p=temp1;
		q=temp2;
	}
	if(typ==2||typ==0)
	{
		dp[x][0]=min(p,make_pair(q.first+1,q.second));
	}else
	{
		dp[x][0]=make_pair(INF,INF);
	}
	if(typ==2||typ==1)
	{
		dp[x][1]=min(make_pair(p.first+1,p.second+1),make_pair(q.first,q.second+1));
	}else
	{
		dp[x][1]=make_pair(INF,INF);
	}
}
int main()
{
  freopen("w.in","r",stdin);
  freopen("w.out","w",stdout);
  scanf("%d",&n);
  init();
  for(int i=1;i<n;i++)
    {
      int x,y,z,w;
      scanf("%d%d%d%d",&x,&y,&z,&w);
      if(w==2)
      {
      	add(x,y,w);
      	add(y,x,w);
	  }else
      {
      	add(x,y,w^z);
      	add(y,x,w^z);
	  }
    }
    dfs(1,1,0);
    printf("%d %d\n",dp[1][0].first/2,dp[1][0].second);
  return 0;
}

巴特西

雅礼 noip2018 模拟赛 day3 T3

最新文章

热门文章