ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1471. Расстояние в дереве

whay i got TLE
Послано Beautiful Mind 26 сен 2006 15:21

  I don't know why i got TLE in test 3. I used simple bfs , as
 its a tree . can any one tell me is it ok? I used template library heavily. if my method is wrong ,then what's the correct algorithm? plz , help me.
Re: whay i got TLE
Послано iezahel 26 сен 2006 22:56
If you use BFS for every query, the complexity is O(N*M) which is too big. I will give you some hints:
1) Root the tree(just make proper father-son relations)
2) Find the distance from the root node to the other nodes
3) Now for any 2 nodes x, y consider the node z, which is
their Least Common Ancestor, and how could this node help you
to find the distance between x and y.
Re: whay i got TLE
Послано Beautiful Mind 29 сен 2006 20:16
Re: whay i got TLE
Послано Beautiful Mind 29 сен 2006 20:19

 thanks. I will try to learn LCA as soon as i can . Thanks again for ur replay.
Re: whay i got TLE
Послано FuckTheBrainUSA 1 авг 2008 06:22
i have the same problem with 3rd test.
But i use first DFS to find distance between root (0 node) and all another nodes. (N + N)
Then use LCA (N*LOG(N))

and eventually get TLE 3

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define RS(x,n) x.resize(n);

vector<int> used;
vector<int> tin;
vector<int> tout;
vector<vector<int> > up;
vector<int> dist;

struct edge
{
    int value;
    int vert;
    edge(){};
    edge(int v, int ve)
    {
        vert=v;
        value = ve;
    }
};

vector<vector<edge> > edges;
bool operator>(const edge & a,const edge & b)
{
    return (a.value > b.value);
}

int n,m; // количество вершин и запросов

void input()
{
    cin >> n;
    int a,b,v;
    edges.resize(n);
    for(int i=0;i<n-1;i++)
    {
        cin >> a >> b >> v;
        edges[a].push_back(edge(b,v));
        edges[b].push_back(edge(a,v));
    }
}
int maxValue = 1e9;
void deijkstra()
{
    priority_queue<edge,vector<edge>,greater<edge> > p;
    p.push(edge(0,0));
    used.resize(n+1);
    dist.assign(n+1,maxValue);
    dist[0] = 0;
    while(! p.empty())
    {
        edge cur = p.top(); p.pop();
        if (used[cur.vert])
            continue;
        used[cur.vert] = 1;
        for(int i = 0 ;i < edges[cur.vert].size();i++)
        {
            edge next = edges[cur.vert][i];
            if (dist[next.vert] > dist[cur.vert] + next.value)
            {
                dist[next.vert] = dist[cur.vert] + next.value;
                p.push(edge(next.vert,dist[next.vert]));
            }
        }
    }
}

int l;
int timer;

bool upper(int a, int b)
{
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int LCA(int f, int s)
{
    if (upper(f,s)) return f;
    if (upper(s,f)) return s;
    for(int i = l ; i >= 0; i--)
        if (!upper(up[f][i],s))
            f = up[f][i];

    return up[f][0];
}

void dfs(int vert, int p = 0)
{
    used[vert] = 1;
    tin[vert] = ++ timer;
    up[vert][0] = p;
    for(int i=1;i<=l;i++)
        up[vert][i] = up[up[vert][i-1]][i-1];

    for(int i=0;i<edges[vert].size();i++)
    {
        int next = edges[vert][i].vert;
        if (!used[next])
            dfs(next,vert);
    }
    tout[vert] = ++ timer;
}

void prepare_lca()
{
    tin.assign(n+1,0);
    tout.assign(n+1,0);
    up.resize(n+1);
    used.assign(n+1,0);
    while( (1 << l) <= n) l++;
    //l++;
    for(int i=0;i<n;i++)
        RS(up[i],l+1);

    dfs(0);
}

void find(int vert,int sum = 0)
{
    used[vert] = 1;
    dist[vert] = sum;
    for(int i=0;i<edges[vert].size();i++)
    {
        edge next = edges[vert][i];
        if (!used[next.vert])
            find(next.vert,sum + next.value);
    }
}

void solve()
{
    //deijkstra();
    used.assign(n+1,0);
    dist.assign(n+1,maxValue);
    dist[0] = 0;
    find(0);

    cin >> m;
    int f,s;
    prepare_lca();

    for(int i=0;i<m;i++)
    {
        cin >> f >> s;
        int lca = LCA(f,s);
        cout << dist[f] + dist[s] - 2*dist[lca] << "\n";
    }

}

int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    input();
    solve();
    return 0;
}
iezahel писал(a) 26 сентября 2006 22:56
If you use BFS for every query, the complexity is O(N*M) which is too big. I will give you some hints:
1) Root the tree(just make proper father-son relations)
2) Find the distance from the root node to the other nodes
3) Now for any 2 nodes x, y consider the node z, which is
their Least Common Ancestor, and how could this node help you
to find the distance between x and y.
Re: whay i got TLE
Послано Abzal 22 авг 2011 23:49
we shouldn't use Dijkstra. because the graph is tree, so path is unique, so shortest path too. for finding shortest path we can use BFS