ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1471. Distance in the Tree

whay i got TLE
Posted by Beautiful Mind 26 Sep 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
Posted by iezahel 26 Sep 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
Posted by Beautiful Mind 29 Sep 2006 20:16
Re: whay i got TLE
Posted by Beautiful Mind 29 Sep 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
Posted by FuckTheBrainUSA 1 Aug 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 wrote 26 September 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
Posted by Abzal 22 Aug 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