• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AT4434 [ARC103D] Distance Sums

开发技术 开发技术 7天前 5次浏览

由题显然有:

[begin{cases}

siz_u=1+sum_{vin son_u} siz_v \

d_v=d_u+n-2times siz_v

end{cases}]

顺带一提,(d) 是 换根dp 的基操。

因为我们知道 (d) , 所以考虑将 (siz) 消掉,从而确定父子关系。

化简可得:

[frac{d_{fa}+n-d_u}{2}=1+sum_{vin son_u} frac{d_u+n-d_v}{2}
]

[d_{fa}+n-d_u=2+sum_{vin son_u} d_u+n-d_v
]

[d_{fa}=d_u+2-n+sum_{vin son_u} d_u+n-d_v
]

可以发现,(d) 最大的节点一定是叶子,并且对于叶子 (u) 的父亲的 (d),满足

[d_{fa}=d_u+2-n
]

那么可以把 (d) 从大到小排序,维护对父亲的贡献即可。

注意我们构造出的这棵树只满足父子 (d) 的差值,所以还要遍历这棵树判断根的 (d) 是否与题目相同。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long

const int MAXN = 1e6;
int n , fa[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
struct node {
    int id; LL d , f;
    bool operator < ( const node &x ) const { return d > x.d; }
    bool operator > ( const node &x ) const { return d < x.d; }
    bool operator > ( const LL &x  ) const { return d < x; }
    bool operator < ( const LL &x  ) const { return d > x; }
}p[ MAXN + 5 ];

int rt; LL disrt;
void dfs( int u , int dep ) {
	disrt += dep;
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) dfs( Graph[ u ][ i ] , dep + 1 );
}

int main( ) {
    scanf("%d",&n);
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&p[ i ].d) , p[ i ].id = i;
	sort( p + 1 , p + n + 1 );
    for( int i = 1 ; i < n ; i ++ ) {
        fa[ i ] = lower_bound( p + 1 , p + n + 1 , p[ i ].d + 2 - n + p[ i ].f ) - p;
        if( fa[ i ] == n + 1 ) return printf("-1n") & 0;
        Graph[ fa[ i ] ].push_back( i );
        p[ fa[ i ] ].f += p[ fa[ i ] ].d + n - p[ i ].d;
    }
    for( int i = 1 ; i <= n ; i ++ ) if( !fa[ i ] ) rt = i;
    dfs( rt , 0 ); if( disrt != p[ rt ].d ) return printf("-1n") & 0;
    for( int i = 1 ; i < n ; i ++ ) if( fa[ i ] ) printf("%d %dn", p[ fa[ i ] ].id , p[ i ].id );
    return 0;
}

程序员灯塔
转载请注明原文链接:AT4434 [ARC103D] Distance Sums
喜欢 (0)