• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送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}]

[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_{fa}=d_u+2-n
]

``````#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;
}
``````