[bzoj2657][Zjoi2012]旅游 journey_ 对偶图_树形dp

旅游 bzoj-2657 Zjoi-2012

题目大意：题目链接

注释：$1\le K\le 2\cdot 10^5$。

---

想法：这题...

感觉和上一个题的提示有些类似，就是题目生怕你不知道这是一道对偶图的题... ...

我们先把它转成对偶图。然后我们只把分割n变形的线段两侧的点之间连边，这样就是一棵树。

紧接着我们想要遍历最多的城市，其实就是找树上直径。树形dp即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200010

using namespace std;

int to[N<<1],nxt[N<<1],head[N],joa;

int tot[(N<<1)+N],f[N][2],cnt;

struct Node

{

	int x,y,p;

}edge[(N<<1)+N];

inline bool cmp(const Node &x,const Node &y)

{

	return x.x==y.x?x.y<y.y:x.x<y.x;

}

inline void add(int x,int y)

{

	to[++joa]=y;

	nxt[joa]=head[x];

	head[x]=joa;

}

int ans=0;

void dfs(int pos,int fa)

{

	for(int i=head[pos];i;i=nxt[i])

	{

		if(to[i]==fa) continue;

		dfs(to[i],pos);

		if(f[pos][0]<f[to[i]][0]+1) f[pos][1]=f[pos][0],f[pos][0]=f[to[i]][0]+1;

		else f[pos][1]=max(f[pos][1],f[to[i]][0]+1);

	}

	ans=max(ans,f[pos][0]+f[pos][1]);

}

int main()

{

	int n; cin >> n ;

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

	{

		int x,y,z;

		scanf("%d%d%d",&x,&y,&z);

		edge[++cnt].x=min(x,y),edge[cnt].y=max(x,y); edge[cnt].p=i;

		edge[++cnt].x=min(x,z),edge[cnt].y=max(x,z); edge[cnt].p=i;

		edge[++cnt].x=min(y,z),edge[cnt].y=max(y,z); edge[cnt].p=i;

	}

	sort(edge+1,edge+cnt+1,cmp);

	for(int i=1;i<=cnt;i++)

	{

		// printf("%d %d %d\n",edge[i].x,edge[i].y,edge[i].p);

		if(i==1||abs(edge[i].x-edge[i].y)==1||(edge[i].x==1&&edge[i].y==n)) continue;

		if(edge[i].x==edge[i-1].x&&edge[i].y==edge[i-1].y)

		{

			// printf("Fuck %d %d\n",edge[i-1].p,edge[i].p);

			add(edge[i].p,edge[i-1].p);

			add(edge[i-1].p,edge[i].p);

		}

	}

	dfs(1,1);

	// for(int i=1;i<=n-2;i++)

	// {

	// 	printf("%d %d\n",f[i][0],f[i][1]);

	// }

	printf("%d\n",ans+1);

	return 0;

}

小结：裙子课件什么题都有qwq/hy