Untitled

 
 
#include <unordered_map>
#include <algorithm>
 
 
using namespace std;
 
 
struct Device
{
    int id;
 
 
    int tree_depth;    // depth from root to node
    int root_delay; // distance from root to node
     
    Device* parent; // parent
    int parent_delay; // distance between parent and node
     
    int max_delay[2]; // the farthest distance from the node to the child direction. Manage 1st and 2nd.
    Device* max_delay_device[2]; // The child on the path with the farthest distance from the node to the child direction. Manage 1st and 2nd.
 
 
    /* Initialize */
    void init(int _id)
    {
        id = _id;
        parent = nullptr;
        parent_delay = 0;
         
        tree_depth = 0;
        root_delay = 0;
 
 
        max_delay[0] = max_delay[1] = 0;
        max_delay_device[0] = max_delay_device[1] = nullptr;
    }
     
    /* Update max_delay[] and max_delay_device[]. */
    void update()
    {
        int delay = parent_delay;
 
 
        Device* ptr = this;
        while (ptr->parent)
        {
            if (ptr->parent->max_delay_device[0] == ptr) // When the child having the farthest distance from the parent is the corresponding equipment
            {
                if (ptr->parent->max_delay[0] < delay)
                    ptr->parent->max_delay[0] = delay;
                else
                    break;
            }
            else if (ptr->parent->max_delay[0] < delay) // When the equipment has a farther distance than the child who has the farthest distance from the parent
            {
                ptr->parent->max_delay[1] = ptr->parent->max_delay[0];
                ptr->parent->max_delay_device[1] = ptr->parent->max_delay_device[0];
                ptr->parent->max_delay[0] = delay;
                ptr->parent->max_delay_device[0] = ptr;
            }
            else if (ptr->parent->max_delay[1] < delay) // When the equipment has a farther distance than the second child who has the farthest distance from the parent
            {
                ptr->parent->max_delay[1] = delay;
                ptr->parent->max_delay_device[1] = ptr;
            }
            else
            {
                break;
            }
 
 
            /* Change the position of the node to the parent position. Increase the distance by the distance between the parent and the node. */
            delay += ptr->parent->parent_delay;
            ptr = ptr->parent;
        }
    }
     
    /* Add a child. */
    void add(Device* child, int latency)
    {
        child->parent = this;
        child->parent_delay = latency;
         
        child->tree_depth = tree_depth + 1;
        child->root_delay = root_delay + latency;
 
 
        child->update();
    }
     
    /* Find the longest path from that node.
       The idea is that if there is a path with the maximum distance, it is a path going in the direction of one or two children of a piece of equipment and this device is between the monitoring device and the root device. */
    int test()
    {
        int ret = 0;
        int monitoring_delay = 0; // The farthest distance along the route starting from the node in the direction of the child and passing through the monitoring equipment
        Device* monitoring_delay_device = nullptr; // A child who has the farthest distance along the path from the node to the child's direction and passes through the monitoring equipment
         
        // When the node is the monitoring equipment
        ret = max_delay[0];
        monitoring_delay = max_delay[0];
        monitoring_delay_device = max_delay_device[0];
     
        Device* ptr = this;
        while (ptr)
        {
            if (ptr->max_delay[1] > 0) // has the second longest distance
            {
                int candidate = monitoring_delay + (ptr->max_delay_device[0] != monitoring_delay_device ? ptr->max_delay[0] : ptr->max_delay[1]);
                ret = max(ret, candidate);
            }
            else // doesn't have the second longest distance
            {
                ret = max(ret, monitoring_delay);
            }
 
 
            // Change the location of the node to the parent location. Change the monitoring_delay and monitoring_delay_device accordingly.
            monitoring_delay += ptr->parent_delay;
            monitoring_delay_device = ptr;
            ptr = ptr->parent;
        }
         
        return ret;
    }
};
 
 
int nn;
Device devices[10001];
 
 
Device* getDevice()
{
    return &devices[nn++];
}
 
 
Device* root;
 
 
unordered_map<int, Device*> cdb;
 
 
void init(int mDevice)
{
    cdb.clear();
 
 
    nn = 0;
     
    root = getDevice();
    root->init(mDevice);
     
    cdb[mDevice] = root;
}
 
 
void connect(int mOldDevice, int mNewDevice, int mLatency)
{
    Device* dev1 = cdb[mOldDevice];
    Device* dev2 = getDevice();
     
    dev2->init(mNewDevice);
    dev1->add(dev2, mLatency);
     
    cdb[mNewDevice] = dev2;
}
 
 
int measure(int mDevice1, int mDevice2)
{
    Device* dev1 = cdb[mDevice1];
    Device* dev2 = cdb[mDevice2];
     
    if (dev1->tree_depth < dev2->tree_depth)
        swap(dev1, dev2);
     
    int ret = 0;
    int d = dev1->tree_depth - dev2->tree_depth;
    while (d--)
    {
        ret += dev1->parent_delay;
        dev1 = dev1->parent;
    }
     
    while (dev1 != dev2)
    {
        ret += dev1->parent_delay + dev2->parent_delay;
        dev1 = dev1->parent;
        dev2 = dev2->parent;
    }
 
 
    return ret;
}
 
 
int test(int mDevice)
{
    Device* dev = cdb[mDevice];
 
 
    return dev->test();
}