[BZOJ1758] [WC2010] 重建計劃 - 樹分治

1758: [Wc2010]重建計劃

Time Limit: 40 Sec   Memory Limit: 162 MB

Submit: 2178   Solved: 700

[ Submit][ Status][ Discuss]

Description

Input

第一行包含一個正整數N，表示X國的城市個數. 第二行包含兩個正整數L和U，表示政策要求的第一期重建方案中修建道路數的上下限 接下來的N-1行描述重建小組的原有方案，每行三個正整數Ai,Bi,Vi分别表示道路(Ai,Bi),其價值為Vi 其中城市由1..N進行标号

Output

輸出最大平均估值，保留三位小數

Sample Input

4

2 3

1 2 1

1 3 2

1 4 3

Sample Output

2.500

HINT

20%的資料,N<=5000

30%的資料,N<=100000,原有方案恰好為一條路徑

100%的資料,N<=100000,1<=L<=U<=N-1,Vi<=1000000

Source

[ Submit][ Status][ Discuss] 

HOME   Back

        樹分治的題怎麼都輕易地這麼煩啊qwq。

upd.正解應該是樹分治+單調隊列 之前一直不知道自己為什麼能過 現在有hack資料了 下面的做法正确性的确不能保證 向所有看過我代碼的人緻歉…

        樹分治就不用說了，主要是work比較難寫。首先我們考慮每層分治換根後，對于根x的所有子節點（删除的不算）進行dfs，求出每個點到根的距離，隸屬的子樹根節點（x的子節點）和對答案的貢獻（注意貢獻要longlong）

        然後我們考慮如何在統計答案。考慮對于一條到根的路徑，如果其本身就在L-U範圍内，顯然求一次max。否則我們考慮的範圍就是不在此子樹的結點中長度在max(L-len,1)~min(U-len,maxlen)中。顯然我們可以用線段樹存儲長度為x的最大答案和與最大答案子樹不同的最大答案，可以證明隻會用到這兩個答案。

        時間複雜度O(nlognlogS)，其中S為子樹平均深度。

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const int L=3000005;
char _buff[L]; int _pos=-1;
void ReadIn(){fread(_buff,L,sizeof(char),stdin);}
#define fge _buff[++_pos]
inline int read(){
	int x=0,f=1; char ch=fge;
	while(ch>'9'||ch<'0')
	{if(ch=='-')f=-1;ch=fge;}
	while(ch<='9'&&ch>='0')
		x=x*10+ch-'0',ch=fge;
	return x*f;
}

const int N=100005;
struct P{
	int v,c;
	P(int _=0,int __=0)
	{v=_,c=__;}
};
vector<P>e[N];
struct Data{
	int len,ffa;ll sval;
	Data(int _=0,ll __=0,int ___=0)
	{ len=_; sval=__; ffa=___;}
	bool operator <(const Data&a)const
	{ return sval*(ll)a.len<a.sval*(ll)len;}
	Data operator +(const Data&a)const
	{ return Data(len+a.len,sval+a.sval,ffa);} 
} q[N] ,ans;
bool cmplen(const Data&a,const Data&b)
{ return a.len<b.len;}

int n,size[N],mnr,mxr,c,maxlen;
bool f[N],v[N];

void dfs(int x){
	v[x]=true;size[x]=1;int i;
	for(i=0;i<e[x].size();i++){
		int to=e[x][i].v;
		if(!f[to]&&!v[to]){
			dfs(to);
			size[x]+=size[to];
		}
	}
	v[x]=false;
}

int getweight(int x){
	dfs(x);bool move=true;
	int m=size[x],i,to,fn;
	while(move){
		move=false;
		for(i=0;i<e[x].size();i++){
			to=e[x][i].v;
			if(size[to]>size[x])continue;
			if(size[to]>m/2&&!f[to]){
				x=to;
				move=true;
				break;
			}
		}
	}
	return x;
}

void BuildData(int x,int fa,int d,ll scost){
	int i,to,cost;q[++c]=Data(d,scost,fa);
	for(v[x]=true,i=0;i<e[x].size();i++){
		to=e[x][i].v;cost=e[x][i].c;
		if(f[to]||v[to]) continue;
		BuildData(to,fa,d+1,scost+cost);
	}v[x]=false; maxlen=max(maxlen,d);
}

struct Node{
	Data larg,slar;
	Node (Data _=Data(N,0,0),Data __=Data(N,0,0))
	{ larg=_; slar=__;}
	void update(Node a,Node b){
		larg=max(a.larg,b.larg);
		if(a.larg.ffa!=larg.ffa)slar=max(slar,a.larg);
		else if(a.slar.ffa!=larg.ffa)slar=max(slar,a.slar);
		if(b.larg.ffa!=larg.ffa)slar=max(slar,b.larg);
		else if(b.slar.ffa!=larg.ffa)slar=max(slar,b.slar);
	}
} d[4*N];
int pl[N];

void buildpl(int v,int l,int r){
	d[v]=Node();int mid=(l+r)>>1;
	if(l==r){pl[l]=v;return;}
	buildpl(v<<1,l,mid);
	buildpl(v<<1|1,mid+1,r);
}

void buildtr(int v,int l,int r){
	int mid=(l+r)>>1;
	if(l==r){return;}
	buildtr(v<<1,l,mid);
	buildtr(v<<1|1,mid+1,r);
	d[v].update(d[v<<1],d[v<<1|1]);
}

Node ask(int v,int l,int r,Node&dt){
	int _l=mnr-dt.larg.len,_r=mxr-dt.larg.len;
	if(_r<=0||_l>maxlen)return Node(Data(),Data());
	_l=max(_l,l);_r=min(_r,r);
	if(_l>_r)return Node(Data(),Data());
	Node ret=Node(Data(1,N*1000,dt.larg.ffa),Data(N,0,0));int mid=(l+r)>>1;
	if(l>=_l&&r<=_r){ret.update(ret,d[v]);return ret;}
	if(_r<=mid)return ask(v<<1,l,mid,dt);
	if(_l>mid) return ask(v<<1|1,mid+1,r,dt);
	ret.update(ask(v<<1,l,mid,dt),ask(v<<1|1,mid+1,r,dt));
	return ret;
}

void work(int x){
	c=maxlen=0;v[x]=true;int i,to,cost,j;
	fill(q+1,q+size[x],Data());
	for(i=0;i<e[x].size();i++){
		to=e[x][i].v;cost=e[x][i].c;
		if(f[to]||v[to]) continue;
		BuildData(to,to,1,cost);
	} if(maxlen==0)return;
	fill(d+1,d+maxlen*2,Node());
	buildpl(1,1,maxlen);
	for(i=1;i<=c;i++){
		d[pl[q[i].len]].update(d[pl[q[i].len]],Node(q[i],Data(N,0,0)));
	} buildtr(1,1,maxlen);
	for(i=1;i<=maxlen;i++){
		Node th=ask(1,1,maxlen,d[pl[i]]);
		if(th.larg.len)
		ans=max(ans,th.slar+d[pl[i]].larg);
		if(i>=mnr&&i<=mxr)
		ans=max(ans,d[pl[i]].larg);
	}
}

void TreeConquer(int x){
	x=getweight(x);work(x);int i,to;
	for(f[x]=true,i=0;i<e[x].size();i++){
		to=e[x][i].v;
		if(f[to]) continue;
		TreeConquer(to);
	}
}

int main(){
	ReadIn();n=read();int i,u,v,c;
	for(mnr=read(),mxr=read(),i=1;i<n;i++){
		u=read(),v=read(),c=read();
		e[u].push_back(P(v,c));
		e[v].push_back(P(u,c));
	} ans=Data(N,0,0); TreeConquer(1);
	printf("%.3lf\n",(double)ans.sval/ans.len);
	return 0;
}