Spiders



ერთ დღეს დედამ დაჩის სთხოვა სათამაშოები გადაერჩია და ზოგი მათგანი გადაეყარა. დაჩიმ სათამაშო ობობებით სავსე ყუთი იპოვა. ბიჭუნას ძალიან უყვარდა თავისი თოჯინები და არ უნდოდა მათთან განშორება, ამიტომაც, მზაკვრული გეგმა მოაფიქრდა : იგი ყველა ობობას ერთმანეთს შეაწებებდა და ჭერზე ააკრავდა. დაჩიმ იცოდა, რომ რაც უფრო დაბლა ეკიდებოდნენ მისი ობობები, მით უფრო ნაკლებად გაბზარდებოდა დედა და შესაბამისად, არ გადააყრევინებდა მას სათამაშოებს. თქვენი მიზანია, დაეხმაროთ დაჩის, სისრულეში მოიყვანოს თავისი გეგმა.

ობობა შედგება K ცალი ბურთულასგან, რომლებიც, K-1 ძაფით არიან დაკავშირებულნი. თითო ძაფი ორ ბურთულას აერთებს და ბურთულების ნებისმიერი წყვილი ერთმანეთს პირდაპირ ერთი ძაფით, ან ბურთულათა და ძაფთა რაღაც ჯაჭვით უკავშირდება.


დაჩის ობობების გადაბმა პირდაპირ ბურთულებით შეუძლია, ხოლო თითო ძაფის ზომა 1-ის ტოლია, ბურთულათა ზომებს არ ვითვალისწინებთ, ამიტომაც ნებისმიერი ბურთულა შეიძლება ნებისმიერს გადაებას. მეტიც, ობობების გადაბმით მიღებული კონსტრუქცია ასევე ობობას უნდა წარმოადგენდეს, ანუ წინა აბზაცში ნახსენებ თვისებებს უნდა ფლობდეს.

იმის შემდეგ, რაც დაჩი ყველა ობობას გადააბამს ერთმანეთს, იგი გაზომავს მიღებულ სათამაშოს. სიგრძეს განვმარტავთ, როგორც რაოდენობას ძაფებისა, რომლებიც ორ ბურთულას აკავშირებენ. ხოლო საბოლოო კონსტრუქციის სიგრძე ბურთულების ყველა წყვილის სიგრძეებს შორის უდიდესის ტოლია. დაჩის სურს, რომ მიიღოს ობობა, რომელსაც მასქიმალური სიგრძე ექნება.

 

სურათზე გამოსახულია ორი ობობა, შეგვიძლია, რომ ისინი პირველის (2) და მეორეს (1) ბურთულებით გადავაბათ და მივიღოთ ახალი სათამაშო, რომლის მაქსიმალური სიგრძის მქონე გზაც მუქადაა გამოსახული ნახატზე.

 

 

შემომავალი მონაცემები:

პირველ ხაზში ერთი მთელი რიცხვი  n (1 ≤ n ≤ 100)  ობობების რაოდენობას აღნიშნავს. შემდეგი n ხაზში თითოეული ობობის აღწერას ვხვდებით : ni (2 ≤ ni ≤ 100) - ძაფების რაოდენობა, შემდეგ კი ni -1 ცალი ბურთულათა წყვილი, რომლებსაც ძაფები აკავშირებს. ბურთულები 1-დან ni -მდეა გადანომრილი.

გამომავალი მონაცემები:

დაბეჭდეთ ერთი რიცხვი - საჭირო კონსტრუქციის სიგრძე.

 

მაგალითები

Input

1

3 1 2 2 3

Output
2


Input
2
3 1 2 1 3
4 1 2 2 3 2 4

Output
4
 
Input
2
5 1 2 2 3 3 4 3 5
7 3 4 1 2 2 4 4 6 2 7 6 5

Output
7
 

 


 

ამოცანის ანალიზი

ობობის აღწერიდან გამომდინარე, მარტივია მიხვედრა, რომ საქმე გვაქვს ხის ტიპის გრაფთან, რადგან გვაქვს K წვერო და K-1 წიბო და მეტიც, ნებისმიერ ორ წვეროს შორის არსებობს გზა. თუ გვინდა, რომ სიგრძე მაქსიმალური იყოს, შეგვიძლია, საბოლოო პასუხი მივიღოთ შემომავალი ობობების (ხეების) სიგრძეების შეკრებით. ხოლო თითოეული ხისთვის სიგრძის დათვლა მარტივია : თითოეული წვეროსთვის გავიგოთ მაქსიმალური სიგრძე, შემდეგ კი მათ შორის ავირჩიოთ უდიდესი. მნიშვნელოვანია ის მომენტი, რომ აუცილებელია, ყველა წიბოსთვის შევამოწმოთ უგრძესი გზა და არა მხოლოდ სათავისთვის.

მაგალითად, მარცხნივ გამოსახულ გრაფში გრაფში (1)-დან რომ დავიწყოთ დათვლა, პასუხად 1-ს მივიღებთ. ხოლო (2)-დან ან (3)-დან რომ დავითვალოთ, პასუხი 2 იქნება. ჩვენ კი მაქსიმალური გვჭირდება, ამიტომაც მხოლოდ სათავის შემოწმება არ კმარა.

 

ამოცანის ამოხსნა

ამოხსნის რეალიზაცია მარტივად ხერხდება DFS-ით. თითოეული ობობისთვის : თითოეული წვეროდან გავუშვათ DFS, თან ვიმახსოვროთ თუ რამდენი წვერო გაიარა ამ კონკრეტულმა გაშვებამ, თუ ამ გაშვებაზე განვლილი წვეროების რაოდენობა მეტია საერთო მაქსიმუმზე (ყველა გაშვებებიდან მაქსიმალურზე, რომელიც თავიდან 0 იქნება), მაშინ ეს მაქსიმალური მაჩვენებელი გავზარდოთ. ის ფაქტი, რომ გრაფი ხეა, გვიმარტივებს საქმეს, DFS-ს უნდა გადავცეთ ერთი დამატებითი პარამეტრი, წინა (მშობელი) წვეროს აღმნიშვნელი რიცხვი, რომლის მეშვეობითაც თავს ავირიდებთ დამატებითი მასივის შემოღებას, რომელშიც დავიმახსოვრებდით უკვე ნამყოფ წვეროებს.

 

ამოხსნის კოდი

#include <vector>
#include <iostream>
using namespace std;

#define maxSize 105
vector<int> graph[maxSize];
int nTrees, numVerts, firstVertex, secondVertex;

void buildGraph() {
    cin >> numVerts;
    for (int i = 0; i < numVerts - 1; i++) {
        cin >> firstVertex >> secondVertex;
        graph[firstVertex].push_back(secondVertex);
        graph[secondVertex].push_back(firstVertex);
    }
}

void clearGraph() {
    for (int i = 0; i < maxSize; i++) {
        graph[i].clear();
    }
}

void DFS(int cur, int parent, int curLength, int &max) {
    if (curLength > max)
        max = curLength;
    for (int neighbour = 0; neighbour < graph[cur].size(); neighbour++) {
        if (graph[cur][neighbour] == parent) continue;
        DFS(graph[cur][neighbour], cur, curLength + 1, max);
    }
}

int calculateLength() {
    int maxLength = 0;
    for (int i = 1; i <= numVerts; i++)
        DFS(i, -1, 0, maxLength);
    return maxLength;
}

int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    int result = 0;
    cin >> nTrees;

    for (int i = 0; i < nTrees; i++) {
        buildGraph();
        result += calculateLength();
        clearGraph();
    }
    cout << result << endl;
}