普通无向图倒是没想到什么好解法，不过大概也可以往这上面贴
by TDoG_W @ 2024-01-09 20:56:48
我们模拟赛考过这题，做到了 $O(n\log n)$。
我抄一下题解：
我们先每个点单独减，这样要花费权值之和的次数。
然后我尝试把某些减合并，对于一个点，我们在上面放权值大小个数的点，一个点上面的点就可以向之多两个相邻的点连边，于是答案就变成了最大匹配。
设 $f_i$ 表示 $i$ 中最多产生多少匹配，$g_i$ 表示在产生匹配数最多的情况下 $i$ 上最多有几个点能和父亲配
对。
转移讨论一下即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=500005,M=1000000007;
int i,n,m,j,a[N],p[N],dp2[N],u,v;
vector<int> g[N];
long long dp[N],s;
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int i,int fa)
{
for(auto it:g[i])
if(it!=fa)
{
dfs(it,i);
dp[i]+=dp[it];
}
int k=0,j;
for(auto it:g[i])
if(it!=fa)
p[++k]=dp2[it];
sort(p+1,p+1+k,cmp);
long long s=0;
for(j=1;j<=k;++j)
{
p[j]=min(p[j],a[i]);
s+=p[j];
}
if(k)
{
if(p[1]>s-p[1])
{
if(a[i]<(s-p[1]))
{
dp2[i]=0;
dp[i]+=a[i]*2;
}
else
{
dp[i]+=(s-p[1])*2+min(a[i],p[1])-(s-p[1]);
if(a[i]<=p[1])
dp2[i]=a[i]-(s-p[1]);
else
dp2[i]=min(2*a[i]-s,1ll*a[i]);
}
}
else
{
dp[i]+=min(a[i]*2ll,s);
dp2[i]=max(0ll,min(2*a[i]-s,1ll*a[i]));
}
}
else
dp2[i]=a[i];
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&a[i]);
s+=a[i];
}
for(i=1;i<n;++i)
{
scanf("%d %d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<s-dp[1];
}
```
by LiWenX @ 2024-01-09 20:58:01
@[TDoG_W](/user/416578)
by LiWenX @ 2024-01-09 20:59:03
@[LiWenX](/user/481476) 树上动规啊/kk
by TDoG_W @ 2024-01-09 20:59:24
@[TDoG_W](/user/416578) 是的吧/jk，排序可以精细实现到线性，直接可以做的理论复杂度下界了。不过没啥用。
by LiWenX @ 2024-01-09 21:02:11
大概想到扩展到基环树上的解法了/蒻
by TDoG_W @ 2024-01-09 21:04:14
我学网络流学傻了/kk
by TDoG_W @ 2024-01-09 21:11:21
P7246
by crimson000 @ 2024-01-09 21:13:10
@[crimson000](/user/755337) thx
by TDoG_W @ 2024-01-09 21:17:47