CF191C Fools and Roads

树上差分的模板题: 在树上差分中,有两种类型. 详情见oi wiki.链接 图为oiwiki的描述,在点差分中,不仅要维护lca,同时还要维护lca的父亲,因为路径是包含lca这个点的. 然而在边差分上,由于把点权下放,所以lca的父亲不必再维护。 需要注意的是,差分是向下边差分的,事实上,这个差分数组起始点是叶子,在还原差分数组的时候,遍历子树,并且对子树求和. 回归这题,显然是边差分的一个模板,套用一下即可.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int fa[maxn][31];int depth[maxn];
void dfs1(int u,int f){
	fa[u][0]=f;depth[u] = depth[f] +1;
	for(int i=1;i>n;
	vector edge;
	for(int i=1;i>u>>v;
		G[u].pb(v);G[v].pb(u);
		edge.push_back({u,v});
	}
	dfs1(1,0);
	cin>>m;
	while(m--){
		int x,y;
		cin>>x>>y;
		d[x]++,d[y]++;
		int f1 = lca(x,y);
		d[f1]-=2;
	}
	dfs(1,0);
	for(auto [u,v]:edge){
		if(depth[u]