#直径#CF804D Expected diameter of a tree

题目

给一片森林，\(q\) 个询问，每个询问两个点，

问将这两个点所在的集合连接起来组成的新集合，它的最远两点的距离的期望值是多少。

分析

首先将以每个点为根的最大深度求出来，然后对于两棵树，

只有超过两棵树直径的最大值才可能产生新的直径，

那么直接求 \(d[x]+d[y]\geq mx\) 的 \(d[x]+d[y]\)，

用小的集合查询然后记忆化就可以做到 \(O(Q\sqrt{n}\log{n})\)

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=100011; typedef long long lll;
map,lll>uk; vectorK[N];
struct node{int y,next;}e[N<<1]; vectorF[N];
int col[N],f[N],g[N],dp[N],as[N],n,m,Q,et=1,upd,len[N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
int max(int a,int b){return a>b?a:b;}
void dfs1(int x,int fa){
	col[x]=upd;
	for (int i=as[x];i;i=e[i].next)
	if (e[i].y!=fa){
		dfs1(e[i].y,x),dp[upd]=max(dp[upd],f[x]+f[e[i].y]+1);
		if (f[x]len[y]) swap(x,y);
		if (uk.count(make_pair(x,y))) {printf("%.8lf\n",uk[make_pair(x,y)]/(1.0*len[x]*len[y])); continue;}
		lll now=max(dp[x],dp[y]),ans=now*len[x]*len[y];
		for (int j=0;j
图论-直径、重心、基环树

相关

标签