「ARC103D」 Distance Sums

传送门

水题。

首先如果让你求树上的节点 \(i\) 到其它所有节点的距离和，这是非常简单的，这就是非常常规的换根 \(\texttt{DP}\)。

那么，我们可以观察一下这个答案的递推式：\(f_u=f_{fa_u}-siz_u+(n-siz_u)\)。

也就是说，如果我们确定了 \(f_u\)，那么我们可以确定 \(f_{fa_u}\) 的值。

又根据递推式，我们可以考虑这样的一种构造方式：

首先将 \(f\) 从大到小排序，如果当前 \(f\) 值未被标记过，则令其为叶子节点，否则将其与对应节点连边。

然后根据递推式将 \(f_u-n+2siz_u\) 标记。

如此，如果不能建出 \(n-1\) 条边，那么肯定不存在合法解。

然后值得注意的几点：

注意我们实际上只是保证了 \(f_{fa_u}-f_u\) 的差值符合题目要求，所以我们需要对我们建出的树任意求出某个点的 \(f\) 来检验正确性。
在 \(f\) 中有两个最小值（即树有两个重心）时依据不同写法可能会有一些细节需要处理。（虽然数据没卡）

贴代码

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=1e5+5;

struct node{

	ll d;ll id;

	bool operator<(const node &h)const{

		return d>h.d;

	}

}p[maxn];

map<ll,int> mp;

ll cnt;

ll num[maxn];

vector<int> e[2*maxn];

vector<pair<int,int> >ans;

vector<int> g[maxn];

ll dis[maxn],siz[maxn];

void dfs(int u,int f){

	siz[u]=1;

	for(auto v:g[u]){

		if(v==f) continue;

		dfs(v,u);

		siz[u]+=siz[v];

		dis[u]+=dis[v]+siz[v];

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	ll n;cin>>n;

	ll owo=0;

	for(ll i=1;i<=n;++i){

		ll x;cin>>x;

		if(i==1) owo=x;

		p[i]=(node){x,i};

	}

	sort(p+1,p+n+1);

	for(ll i=1;i<=n;++i){

		if(!mp.count(p[i].d)){

			mp[p[i].d]=++cnt;

		}

		ll tmp=mp[p[i].d];

		++num[p[i].id];

		while(e[tmp].size()&&((p[i].d-n+2*(num[p[i].id]+num[e[tmp].back()])<=p[i].d)||i==n)){

			ans.emplace_back(e[tmp].back(),p[i].id);

			num[p[i].id]+=num[e[tmp].back()];

			e[tmp].pop_back();

		}

		if(!mp.count(p[i].d-n+2*num[p[i].id])){

			mp[p[i].d-n+2*num[p[i].id]]=++cnt;

		}

		tmp=mp[p[i].d-n+2*num[p[i].id]];

		e[tmp].emplace_back(p[i].id);

	}

	for(auto [x,y]:ans) g[x].emplace_back(y),g[y].emplace_back(x);

	dfs(1,0);

	if((int)ans.size()!=n-1||dis[1]!=owo) cout<<-1<<'\n';

	else

		for(auto [x,y]:ans) cout<<x<<' '<<y<<'\n';

	return 0;

}

巴特西

「ARC103D」 Distance Sums

「ARC103D」 Distance Sums

最新文章

热门文章