bzoj 3302&2447&2103 树的双中心 树形DP

题目:

bzoj 3302&2447&2103 树的双中心 树形DP

题解:

bzoj 3302 == 2447 == 2103 三倍经验

首先我们考虑枚举两个中心的位置,然后统计答案.

我们发现,一定有一部分点离第一个中心更近,另一部分点离第二个中心更近

如果将两部分点分别染成两种颜色,容易发现一定有且只有一条边两端的颜色不相同

所以我们考虑枚举这条边,然后将整个树分成两个部分,然后分别求出分开的两颗树的中心,然后把两部分的代价求和来更新答案.

容易发现这样是\(n^2\)的

然后我们回头看题目,发现有奇怪的条件:深度 <= 100

这启发了我们从深度的角度去考虑.

我们考虑枚举这条边的过程,发现其实我们根本不用枚举所有的边

我们考虑在每一个深度上只枚举一条边

换句话说:我们要选择一条从根开始的链,枚举这条链上的每一条边

我们可以从根考虑来选择每一步走哪一棵子树,从而挑选出一条从根开始的链.

这是我们发现:每一次都走子树权值和最大的哪一棵子树,一定是最优决策.

所以我们可以把复杂度降到\(O(nh)\)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
typedef long long ll;
const ll maxn = 50005;
const ll inf = 1LL<<60;
struct Edge{
ll v,next;
}G[maxn<<1];
ll n, head[maxn], cnt=1,fa[maxn], dep[maxn], mx[maxn], cmx[maxn];
ll sum[maxn],val[maxn],ans=inf,cut;
inline void add(ll u, ll v) {
G[++cnt] = (Edge){v, head[u]};
head[u] = cnt;
}
inline void dfs(ll x) {
for(ll i = head[x];i; i=G[i].next){
if(G[i].v == fa[x]) continue;
dep[G[i].v] = dep[x] + 1;
fa[G[i].v] = x;
dfs(G[i].v);
sum[x] += sum[G[i].v];
val[x] += val[G[i].v] + sum[G[i].v];
if(mx[x] == 0 || sum[G[i].v] > sum[mx[x]]){
cmx[x] = mx[x];
mx[x] = G[i].v;
}else if(cmx[x] == 0 || sum[G[i].v] > sum[cmx[x]]){
cmx[x] = G[i].v;
}
}
}
inline void find(ll &ret,ll root,ll x,ll k){
ret = min(ret,k);
ll v = mx[x];
if(v == cut || sum[cmx[x]] > sum[mx[x]]) v = cmx[x];
if(v == 0) return;
find(ret,root,v, k + sum[root] - 2*sum[v]);
}
inline void dfss(ll x){
for(ll i = head[x];i;i=G[i].next){
if(G[i].v == fa[x]) continue;
cut = G[i].v;
ll gx = inf,gy = inf;
for(ll j = x; j; j = fa[j]) sum[j] -= sum[cut];
find(gx, 1, 1, val[1] - val[cut] - dep[cut] * sum[cut]);
find(gy, cut, cut, val[cut]);
ans = min(ans, gx + gy);
for(ll j = x; j; j=fa[j]) sum[j] += sum[cut];
dfss(G[i].v);
}
}
int main() {
read(n);
for(ll i=1,u,v;i<n;++i){
read(u);read(v);
add(u, v); add(v, u);
}
for(ll i=1;i<=n;++i) read(sum[i]);
dfs(1);dfss(1);
printf("%lld\n",ans);
getchar();getchar();
return 0;
}
上一篇:linux配置server笔记


下一篇:bzoj 1912 : [Apio2010]patrol 巡逻 树的直径