ZROJ1120 树链剖分 – 贪心 – 换根法 –

题目链接：http://zhengruioi.com/problem/1120

题解：
首先如果钦定了根，比如1号点，如何计算答案？
对于路径的部分，显然树上差分一下即可，从下往上每个点贪心，选一个边经过次数最大的边，最后用总数减去最大值即可
如果没有钦定根呢？考虑换根\(u \rightarrow son_u(记为v)\)
显然换根时只会影响u,v两点
如果以u为根时u最优解没有选v，那么只需要考虑v的情况，首先用(u,v)这条边的经过次数更新一下v的最大值和次大值，然后更新一下v的答案
如果u的最优解选了v，那么换根时u需要调整到u的次大值，然后剩下的同上

代码实现细节很多，我怎么又读错题了啊啊啊！！

几个实现上的思路：

1. 用边的序号存每个点的最大值和次大值（代码中存图的时候的second就是边需要）
2. 叶子结点需要单独处理
3. 如果1号点只连了一条边的时候也需要特别考虑
4. 最后处理第二种情况，这样就不需要回溯了

\(ansid\)存的是当前点最优解是哪条边（存边的序号）

不好写。。。

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

vector<pii>g[maxn];
int n,m;
int fa[maxn][22], leaf[maxn], dep[maxn];
pii rans[maxn][2];
int num[maxn], ans = 0, ansid[maxn], cf[maxn];
int res, tot = 0;

void dfs0(int x,int fat=0){
	fa[x][0] = fat;
	dep[x] = dep[fat] + 1;
	for(pii u : g[x]){
		if(u.first == fat)continue;
		dfs0(u.first, x);
	}
	if(fat && g[x].size() == 1)leaf[x] = 1;
}

int getlca(int x,int y){
	if(dep[x] < dep[y])swap(x, y);
	for(int i=20;i>=0;i--){
		if(dep[fa[x][i]] >= dep[y])x = fa[x][i];
	}
	if(x == y)return x;
	for(int i=20;i>=0;i--){
		if(fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}

void dfs1(int x,int fat = 0){
	for(pii u : g[x]){
		if(u.first == fat)continue;
		dfs1(u.first, x);
		num[u.second] += cf[u.first];
		tot += cf[u.first];
		cf[x] += cf[u.first];
	}
	if(leaf[x])return ;
	rans[x][0] = rans[x][1] = mpr(-1e9, 1e9);
	for(pii u : g[x]){
		if(u.first == fat)continue;
		if(num[u.second] > rans[x][0].first)rans[x][1] = rans[x][0], rans[x][0] = mpr(num[u.second], u.second);
		else if(num[u.second] > rans[x][1].first)rans[x][1] = mpr(num[u.second],u.second);
	}
	ans += rans[x][0].first;
	ansid[x] = rans[x][0].second;
}

void getans(int x,int fat = 0,int curans = ans){
	if(x == 1&&g[1].size() == 1){	// corner case 
		int cc = curans;
		pii u = g[1][0];
		int sonu = u.first;
		cc -= rans[x][0].first + rans[sonu][0].first;
		
		if(rans[sonu][0].first < rans[x][0].first){
			ansid[sonu] = rans[x][0].second;
			rans[sonu][1] = rans[sonu][0];rans[sonu][0] = rans[x][0];
		}else if(rans[sonu][1].first < rans[x][0].first)
			rans[sonu][1] = rans[x][0];
		
		cc += rans[sonu][0].first;
		res = max(res, cc);
		
		getans(sonu, x, cc);
		return ;
	}
	
	pii gg =mpr(-1, -1);
	for(pii u : g[x]){
		if(u.first == fat)continue;
		if(leaf[u.first]){	// 叶子结点单独考虑 
			if(ansid[x] != u.second){
				res = max(res, curans + num[u.second]);
			}else{
				if(ansid[x] == rans[x][0].second)
					res = max(res, curans + rans[x][1].first);
				else
					res = max(res, curans + rans[x][0].first);
			}
			continue;
		}
		
		// root : x->u.first
		if(ansid[x] != u.second){	// (x,sonu)没选 
			int sonu = u.first;
			int cc = curans - rans[sonu][0].first;
			if(num[u.second] > rans[sonu][0].first)rans[sonu][1] = rans[sonu][0], rans[sonu][0] = mpr(num[u.second], u.second);
			else if(num[u.second] > rans[sonu][1].first)rans[sonu][1] = mpr(num[u.second], u.second);
			
			ansid[sonu] = rans[sonu][0].second, cc += rans[sonu][0].first;
			
			res = max(res, cc);
			getans(sonu, x, cc);
		}else{	// (x,sonu)选了，最后处理，就不需要再回溯了 
			gg = u;
		}
	}
	
	if(gg.first == -1)return ;
//	printf("!! %d %d\n",x,gg.first);
	pii u = gg;
	int sonu = u.first;
	ansid[x] = rans[x][1].second;
	int cc = curans;
	cc += rans[x][1].first - rans[x][0].first;
	
	if(rans[sonu][0].first < rans[x][0].first){
		ansid[sonu] = rans[x][0].second;
		cc += rans[x][0].first - rans[sonu][0].first;
		rans[sonu][1] = rans[sonu][0];rans[sonu][0] = rans[x][0];
	}else if(rans[sonu][1].first < rans[x][0].first)
		rans[sonu][1] = rans[x][0];
	
	res = max(res, cc);
	getans(u.first, x, cc);
	
	// 除了 sonu 其余的儿子不会更新了，所以不用更新x的 min secmin 
}

signed main(){
//	freopen("zr1120.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(mpr(v,i));
		g[v].push_back(mpr(u,i));
	}
	dfs0(1);
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++)fa[i][j] = fa[fa[i][j-1]][j-1];
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		int lc = getlca(x, y);
		++ cf[x];++ cf[y];cf[lc] -= 2;	// 树上差分 
	}
	dfs1(1);	// 求出 1 为根时的答案 
	
	res = ans;
	getans(1);
	printf("%d\n",tot - res);

	return 0;
}

原文地址：http://www.cnblogs.com/SkyRainWind/p/16897228.html