P2610 [ZJOI2012]旅游 树的直径

这个题就是建图不太好建，但是我们一想，三角形貌似只能两两挨着，最后会变成一个二叉树，所以问题就变成求树的直径。建图用pair套map超级简单。

题干：

到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~

经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，[b]城市组成了关于T国的一个三角剖分[/b])。[b]两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段[/b]。

为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？

输入输出格式

输入格式：

每个输入文件中仅包含一个测试数据。

第一行包含两个由空格隔开的正整数N，N的含义如题目所述。

接下来有N-2行，每行包含三个整数 p,q,r，表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。

输出格式：

输出文件共包含1行，表示最多经过的城市数目。([b]一个城市被当做经过当且仅当其与线路有至少两个公共点[/b])

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<map>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(register int i = a;i <= n;++i)

#define lv(i,a,n) for(register int i = a;i >= n;--i)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

const int N = 2e5 + ;

struct node

{

    int l,r,nxt;

}a[N << ];

int n;

int lst[N],len = ;

void add(int x,int y)

{

//    cout<<x<<" "<<y<<endl;

    a[++len].l = x;

    a[len].r = y;

    a[len].nxt = lst[x];

    lst[x] = len;

    a[++len].l = y;

    a[len].r = x;

    a[len].nxt = lst[y];

    lst[y] = len;

}

int dep[N];

map <pair<int,int>,int> ys;

void dfs(int x,int fa)

{

    dep[x] = dep[fa] + ;

    for(int k = lst[x];k;k = a[k].nxt)

    {

        int y = a[k].r;

        if(y == fa) continue;

        dfs(y,x);

    }

}

int main()

{

    read(n);

    duke(i,,n - )

    {

        int p,q,r;

        read(p);read(q);read(r);

        if(q > p) swap(p,q);

        if(r > p) swap(p,r);

        if(r > q) swap(q,r);

        if(!ys[pair<int,int>(p,q)])

        {

            ys[pair<int,int>(p,q)] = i;

        }

        else

        add(i,ys[pair<int,int>(p,q)]);

        if(!ys[pair<int,int>(p,r)])

        {

            ys[pair<int,int>(p,r)] = i;

        }

        else

        add(i,ys[pair<int,int>(p,r)]);

        if(!ys[pair<int,int>(q,r)])

        {

            ys[pair<int,int>(q,r)] = i;

        }

        else

        add(i,ys[pair<int,int>(q,r)]);

    }

    int root = ;

    dfs(,);

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

    {

        if(dep[i] > dep[root])

        root = i;

    }

//    dep[root] = 0;

    dfs(root,);

    int ans = ;

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

    {

        if(dep[i] > ans)

        ans = dep[i];

    }

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

    return ;

}