【HDU 5452】Minimum Cut(ツリー差分)
本题は処理サイド権:val[u]+,val[v]+,val[lca(u,v)-=2
点権を扱うなら、val[u]+,val[v]+,val[lca(u,v)--,val[fa[lca]--です.
点権を扱うなら、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