【HDU 5452】Minimum Cut(ツリー差分)


本题は処理サイド権:val[u]+,val[v]+,val[lca(u,v)-=2
点権を扱うなら、val[u]+,val[v]+,val[lca(u,v)--,val[fa[lca]--です.
#include
#include
#include
using namespace std;
const int N=2e4+100;
int t,n,m,u,v,x,minn,val[N],sum[N],f[N][16],h[N];
vector e[N];
void dfs(int cur,int fa){
	sum[cur]=val[cur];
	for(int i=0;ih[a])a^=b^=a^=b;
	if(h[a]>h[b]){
		x=h[a]-h[b];
		for(int i=0;i<=15;++i)
			if((1<=0;--i){
		if(f[a][i]!=f[b][i]){
			a=f[a][i];
			b=f[b][i];
		}
	}
	return f[a][0];
}
int main(){
	scanf("%d",&t);
	for(int ca=1;ca<=t;++ca){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i){
			e[i].clear();
			val[i]=0;
			for(int j=0;j<=15;++j)
				f[i][j]=0;
		}
		for(int i=1;i