Cod sursa(job #1243076)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 15 octombrie 2014 16:32:13
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.71 kb
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

struct aur{
    int node,val;
};

aur upDown[100010],downUp[100010];

int N,i,x,y,z,dad[100010],distTata[100010],sol;

vector<pair<int,int> > V[100010];

void DFS(int X)
{
    upDown[X].node = X;
    for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
    {
        int fiu = it->first;
        int dist = it->second;
        if(fiu == dad[X])continue;
        dad[fiu] = X;
        distTata[fiu] = dist;
        DFS(fiu);
        if(upDown[fiu].val + dist > upDown[X].val)
        {
            upDown[X].val = upDown[fiu].val + dist;
            upDown[X].node = upDown[fiu].node;
        }
    }
}
void DFS2(int X)
{
    downUp[X].node = X;
    for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
    {
        int fiu = it->first;
        int dist = it->second;
        if(fiu == dad[X])
        {
            if(downUp[fiu].val + dist > downUp[X].val)
            {
                downUp[X].val = downUp[fiu].val + dist;
                downUp[X].node = downUp[fiu].node;
            }
            if(upDown[fiu].node == upDown[X].node)
                for(vector<pair<int,int> >::iterator jt = V[fiu].begin(); jt != V[fiu].end(); jt++)
                {
                    if(jt->first == X || jt->first == dad[fiu])continue;
                    if(upDown[jt->first].val + distTata[jt->first] + dist > downUp[X].val)
                    {
                        downUp[X].val = upDown[jt->first].val + distTata[jt->first] + dist;
                        downUp[X].node = upDown[jt->first].node;
                    }
                }
            else
            {
                if(upDown[fiu].val + dist > downUp[X].val)
                {
                    downUp[X].val = upDown[fiu].val + dist;
                    downUp[X].node = upDown[fiu].node;
                }
            }
            continue;
        }
    }
    for(vector<pair<int,int> >::iterator it = V[X].begin(); it != V[X].end(); it++)
    {
        int fiu = it->first;
        int dist = it->second;
        if(fiu != dad[X])
            DFS2(fiu);
    }
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i < N; i++)
    {
        scanf("%d%d",&x,&y);
        V[x].push_back(make_pair(y,1));
        V[y].push_back(make_pair(x,1));
    }
    int root = 1;
    DFS(root);
    DFS2(root);
    for(i=1;i<=N;i++)
    {
        sol = max(upDown[i].val,sol);
        sol = max(downUp[i].val,sol);
    }
    printf("%d\n",sol+1);
    return 0;
}