[题解] LuoguP4381 [IOI2008]Island

LuoguP4381 [IOI2008]Island

Description

一句话题意：给一个基环树森林，求每棵基环树的直径长度的和（基环树的直径定义与树类似，即基环树上一条最长的简单路径），节点总数不超过\(10^6\)。

Solution

问题就是如何求基环树的直径。

首先树的直径的话可以直接\(dp\)，那如果有一个环怎么办？

这个环上会挂着几棵树，那么直径只会有两种情况

不经过环上的边，即每棵树直径的最大值
经过一个环，即挂在换上的两棵树\(i,j\)的深度和在加上\(i,j\)在环上的距离

第一种情况直接树形\(Dp\)求一下树的直径就好了。

第二种情况有点麻烦，为了方便下面令\(tree(x)\)表示以\(x\)为根挂在环上的树，\(depth(T)\)表示树\(T\)的深度，\(dist(i,j)\)表示环上两点之间只走环上的边的最大距离（\(i,j\)在环上只有两条路径）。

那这种情况的答案就是\(\max\limits_{i \not= j} \{depth(tree(i)) + depth(tree(j)) + dist(i,j)\}\)

下面令\(v_1,v_2,...,v_s\)表示大小为\(s\)（点的个数）的环上以逆时针或顺时针的访问顺序依次访问到的\(s\)个点，\(sum_i\)表示从\(v_1\)按顺序走走到\(v_i\)的环上路径长度。

那么点\(i\)按一个方向走到点\(j\)的环上长度就是\(sum_j - sum_i\)。

我们可以把环复制两倍，然后就能够处理第\(2\)个方向的距离。

即\(v\)变为\(v_1,v_2,...,v_{s},v_{s+1},...,v_{2s}\)，那么\(v_i\)与\(v_j\)(\(1 \le i<j \le 2s, abs(i-j) < n\))的最大距离\(dist(i,j)\)就是\(max(sum_j - sum_i, sum_{i+s} - sum_j)\)

这样的话就可以单调队列维护，扫一次\(v_{1...2s}\)就行了。

找环的话可以在\(Dfs\)树上找，不卡栈空间的（至少\(Luogu\)是这样......）

Code

#include <bits/stdc++.h>

using namespace std;

template<typename tp> inline void read(tp &x){

	x=0; tp f=1; char ch=getchar();

	for (;!isdigit(ch);ch=getchar())f=ch=='-'?-f:f;

	for (;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

	x=x*f;

}

#define pb push_back

#define same(e1,e2) (min(e1^1,e1)==min(e2^1,e2))

typedef long long ll;

const ll INF=1e18;

const int N=2e6+10;

int cnt=1,fst[N],nxt[N<<1],to[N<<1];ll dis[N<<1];

inline void ade(int x,int y,ll w){

	to[++cnt]=y,nxt[cnt]=fst[x],fst[x]=cnt;

	dis[cnt]=w;

}

inline void addedge(int x,int y,ll w){ade(x,y,w),ade(y,x,w);}

vector<int>ring[N]; int tot=0,dep[N],fa[N];

void dfs(int x,int deep,int lste,int prev){

	dep[x]=deep,fa[x]=prev;

	for (int i=fst[x];i;i=nxt[i]){

		int v=to[i]; //printf("%d->%d\n",x,v);

		if (dep[v]==0) dfs(v,deep+1,i,x);

		else if (!same(i,lste)&&dep[v]<dep[x]){

			++tot;for (int nw=x;nw!=v;nw=fa[nw])ring[tot].pb(nw);

			ring[tot].pb(v);

		}

	}

}

int mark[N];ll dp[N],mxdp;

void DP(int x,int prev){

	for (int i=fst[x];i;i=nxt[i]){

		int v=to[i]; if (mark[v]||v==prev) continue;

		DP(v,x);

		mxdp=max(dp[x]+dp[v]+dis[i],mxdp);

		dp[x]=max(dp[x],dp[v]+dis[i]);

	}

}

int vis[N],id[N],tim;ll a[N],b[N];

void getW(int x,ll dd,int lste){

	vis[x]++,id[++tim]=x,b[tim]=dd;

	for (int i=fst[x];i;i=nxt[i]){

		int v=to[i]; if (!same(i,lste)&&mark[v]&&vis[v]<2)getW(v,dd+dis[i],i);

	}

}

int q[N];

ll solve(int k1){

	int len=ring[k1].size(); ll ans=0;

	for (int i=0;i<len;i++) mark[ring[k1][i]]=1;

	tim=0,getW(ring[k1][0],0,0);

	for (int i=1;i<=len;i++){

		int x=id[i];

		mxdp=0,DP(x,0),ans=max(ans,mxdp);

		a[i]=dp[x];

	}

	for (int i=1;i<=len;i++) a[i+len]=a[i];

	int l=1,r=1; q[l]=1;

	for (int i=2;i<=tim;i++){

		while (l<=r&&i-q[l]>=len)l++;

		int j=q[l]; if (l<=r)ans=max(ans,a[i]+a[j]+b[i]-b[j]);

		while (l<=r&&a[i]-b[i]>a[q[r]]-b[q[r]])r--;

		q[++r]=i;

	}

	return ans;

}

int main(){

	int n;read(n);

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

		int x;ll w; read(x),read(w);

		addedge(x,i,w);

	}

	for (int i=1;i<=n;i++) if (!dep[i])dfs(i,1,0,0);

	ll ans=0;

	for (int i=1;i<=tot;i++)ans+=solve(i);

	printf("%lld\n",ans);

	return 0;

}

巴特西

[题解] LuoguP4381 [IOI2008]Island

Description

Solution

Code

最新文章

热门文章