A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3727 树形$dp$ 数学
发表于: | 分类: Oi | 评论:0 | 阅读:104

$description$

吉丽YY了一道神题,题面是这样的:
“一棵n个点的树,每条边长度为1,第i个结点居住着a[i]个人。假设在i结点举行会议,所有人都从原住址沿着最短路径来到i结点,行走的总路程为b[i]。输出所有b[i]。”
吉丽已经造好了数据,但熊孩子把输入文件中所有a[i]给删掉了。你能帮他恢复吗?

####这真是一神题&……
想了半个小时,还写挂了……最后看了大爷的Blog才发现忘了除2……
首先,如果是给你$a_i$,让你求$b$还是非常简单的,就是经典的$dp+dp$,用之前的$dp$结果进行推
我们还是简单的推导一下
我们可以求出一个点及其子树的$a$的和,设为$sum$
那么从一个点的父亲转移过来就是
$$b[x] = b[fa[x]]+sum[1]-2sum[x]$$
移项得
$$2
sum[x] = b[fa[x]] - b[x] + sum[1]$$
所以我们可以遍历整棵树
求出$sum[x]$ 与 $sum[1]$ 的函数关系

而由原始的定义可知
$$b[1] = \sum{a[i]*dis[i]}$$
我们可以扫一遍,求出$sum[1]$
然后再扫一遍,用$sum_1$求出$a_2,a_3,...a_n$
将他们都减去,就得到了$a_1$
$Orz$神奇的波兰人……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 300000+5  ;
const int M = 600000+5  ;
typedef long long LL;

int head[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int dis[N];
LL a[N],b[N];
int fa[N];

struct Lux
{
    LL a,b;
    Lux () {a=b=0;}
    Lux (LL _a,LL _b):a(_a),b(_b){}
}tmp[N],tmp2[N],tmpb1;
Lux operator + (const Lux &a,const Lux &b){return Lux(a.a+b.a,a.b+b.b);}
Lux operator - (const Lux &a,const Lux &b){return Lux(a.a-b.a,a.b-b.b);}
Lux operator * (const Lux &a,LL y) {return Lux(a.a*y,a.b*y);}

queue <int> q;

void DFS(int x,int val)
{
    q.push(x);dis[x] = val;
    while(!q.empty())
    {
        int tt = q.front();q.pop();
        for(int i=head[tt];i;i=edge[i].next)
            if(edge[i].to!=fa[tt])
            {
                fa[edge[i].to] = tt;
                dis[edge[i].to] = dis[tt] + 1;
                q.push(edge[i].to);
            }
    }
}

inline LL read()
{
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read();
    for(int i=1;i<n;++i)
    {
        int x = read() ,y = read();
        add(x,y);
    }
    for(int i=1;i<=n;++i)
        b[i] = read();
    fa[1] = 1;
    DFS(1,0);
    LL ans = 0;
    for(int i=2;i<=n;++i)
        tmp[i] = Lux(1,b[fa[i]]-b[i]);  

    for(int x=2;x<=n;++x)
    {
        tmp2[x] = tmp[x] ;
        for(int i=head[x];i;i=edge[i].next)
            if(edge[i].to!=fa[x])
                tmp2[x] = tmp2[x] - tmp[edge[i].to];
        tmpb1 = tmpb1 + tmp2[x]* dis[x];
    }
    
    ans = (2*b[1]-tmpb1.b)/tmpb1.a;
    a[1] = ans;
    for(int i=2;i<=n;++i)
    {
        a[i] = (tmp2[i].a*ans + tmp2[i].b)>>1;
        a[1] -= a[i];
    }
    for(int i=1;i<n;++i)
        printf("%lld ",a[i]);
    printf("%lld",a[n]);
}

![](/BZOJ/_image/BZOJ 3727 树形dp 数学/2014-12-10_12-55-48.jpg)

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP