简单树上问题の笔记

树上差分，dfs栈，dfs做差，树上倍增
有8道题

---

A.

一棵含N个结点的树，有K条路径，求结点被经过的最大次数。
非常明显的树上差分：对于每一个节点i，都用pre[i]储存这个节点及其所有祖先节点的遍历次数，此时对每一条路径(u,v)进行分析：

• pre[u]++,pre[v]++;
• lca(u,v)只被遍历一次，但被加了两次, pre[lca(u,v)]—;
• lca(u,v)的祖先节点不会被遍历，但被加了两次（还剩一次）,pre[par[lca(u,v)][0]]—;

得到代码如下：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=100005;

ll n,k;
vector<ll> e[N];

ll par[N][25];
ll dep[N];

ll ans;

void dfs(ll x,ll f)
{
	par[x][0]=f;
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;
		}
		dep[y]=dep[x]+1;
		dfs(y,x);
	}
}


ll LCA(ll x,ll y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	
	for(ll i=0;i<20;i++)
	{
		if((dep[x]-dep[y])>>i&1)
		{
			y=par[y][i];
		}
	}
	
	if(x==y)
	{
		return x;
	}
	
	for(ll i=19;~i;i--)
	{
		if(par[x][i]!=par[y][i])
		{
			x=par[x][i],y=par[y][i];
		}
	}
	
	return par[x][0];
}

ll pre[N];

void dfs2(ll x,ll f)
{
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;
		}
		
		dfs2(y,x);
		pre[x]+=pre[y];
	}
	
	ans=max(ans,pre[x]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>k;
	for(ll i=1;i<n;i++)
	{
		ll x,y;
		cin>>x>>y;
		
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	dfs(1,0);
	for(ll j=1;j<20;j++)
	{
		for(ll i=1;i<=n;i++)
		{
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}
	
	while(k--)
	{
		ll x,y;
		cin>>x>>y;
		
		ll l=LCA(x,y);
		pre[x]++,pre[y]++;
		pre[l]--,pre[par[l][0]]--;
	}
	
	dfs2(1,0);
	
	cout<<ans<<"\n";
	
	return 0;
}

---