学步园

这次比赛莫名其妙地YY两题A,B，速度一般，赛后好好整理了一番。

A 我们如何保证所有段抑或和不等于零呢，    假设前缀i和j的抑或和为Si和Sj,  那么对于任意的(i<j)  必须满足Sj^Si != 0，也就是说假如我要选第i个位置的数，那么这个数不能选的数为第1,2,3，......i-1的前缀抑或和，一共能选2^m-1个数

所以 答案就是  (2^m-1-1) (2^m-1-2)..... (2^m-1-n)

B最大值和最小值是相对比较独立的，所以我们让最大值尽可能的小，最小值尽可能的大，a[n]和a[n-1]放在一起就能保证最大值尽可能小，不光是这样，把很多大的放在一起就可以让最大值尽可能小，a[1]和a[2]放在不同堆里面就能让最小值尽可能大，所以放法有两种， a[1]第一堆， 其它第二堆       或者    全部一堆

C 一个点的时候一定是0，  当n>=2时 我们枚举每条边，让这条边把树切成2部分，然后问题就变成了选书上的一个点让这个点到达所有点的费用最小， 假如根为rt， 当前dfs到点u    那么  费用为从rt到所有点的费用   - (rt到u的链上费用1的边数 - 费用为0的边数)

code C：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3003;
int n;
struct Edge {
	int u, v, w, next;
}edge[maxn<<1];
int E, head[maxn];
void init() {
	E = 0;
	memset(head, -1, sizeof(head));
}
void add(int s, int t, int w) {
	edge[E] = (Edge) {s, t, w, head[s]};
	head[s] = E++;
}
int mx;
int dfs(int u, int fa, int val) {
	int i;
	int ret = 0;
	mx = max(mx, val);
	for(i = head[u]; ~i; i = edge[i].next) {
		int v = edge[i].v;
		if(v == fa) continue;
		ret += dfs(v, u, val+(edge[i].w == 1 ? 1 : -1)) + edge[i].w;
	}

	return ret;
}
int main() {
	int i;
	init();
	scanf("%d", &n);
	for(i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y, 0);
		add(y, x, 1);
	}
	if(n == 1) return puts("0"), 0;
	int ans = 1e9;
	for(i = 1; i < E; i+=2) {
		int tp = 0;
		mx = -1e9;
		tp += dfs(edge[i].u, edge[i].v, 0);
		tp -= mx;
		mx = -1e9;
		tp += dfs(edge[i].v, edge[i].u, 0);
		tp -= mx;
		ans = min(ans, tp);
	}
	printf("%d\n", ans);
	return 0;
}