Max distance may be equal 5e4 * 1e3 = 5e7.
I use INF = 1e6 and spent all day to find this bug.

Just use g++

Что_такой_тест_13?

Anyone can give me this test case?

Can anybody tell me test 5,i am getting WA.I have tried my code on many random cases and it works fine.

Code:-

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define bitcount(n) __builtin_popcount(n)
#define DRT()  int t; cin>>t; while(t--)
#define TRACE
#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
using namespace std;
typedef long long int lli;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< ii > vii;
lli modpow(lli a,lli n,lli temp){lli res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;}
//***********************************END OF TEMPLATE*********************************************************************
const int MAX = 50005,MAX2=log2(MAX);
int d[MAX],h[MAX],P[MAX][MAX2],n;
vector<vii> graph(MAX);
void dfs(int u,int p){
    P[u][0]=p;
    h[u]=h[p]+1;
    for(auto k:graph[u]){
        if(k.F==p)d[u]=d[p]+k.S;
        else dfs(k.F,u);
    }
}
void init(){
    for(int i=0;i<n;++i){
        for(int j=0;(1<<j)<n;++j)P[i][j]=-1;
    }
    d[0]=0;
    h[0]=-1;
    dfs(0,0);
    for(int j=1;(1<<j)<n;++j){
        for(int i=0;i<n;++i){
            if(P[i][j-1]!=-1)P[i][j]=P[P[i][j-1]][j-1];
        }
    }
}
int lca(int u,int v){
    if(h[u]>h[v])swap(u,v);
    int l=log2(h[v]);
    for(int i=l;i>=0;--i){
        if(h[v]-(1<<i)>=h[u]&&P[v][i]!=-1)v=P[v][i];
    }
    //u and v at same level
    if(u==v)return u;
    for(int i=l;i>=0;--i){
        if(P[u][i]!=P[v][i]&&P[u][i]!=-1){
            u=P[u][i];
            v=P[v][i];
        }
    }
    return P[u][0];
}
int query(int u,int v){
    int lc = lca(u,v);
    return d[u]+d[v]-2*d[lc];
}
int main(){
    int u,v,w,q;
    si(n);
    loop(i,1,n){
        si(u);si(v);si(w);
        graph[u].PB(MP(v,w));
        graph[v].PB(MP(u,w));
    }
    init();
    si(q);
    while(q--){
        si(u);si(v);
        printf("%d\n",query(u,v));
    }
    return 0;
}

Edited by author 17.01.2016 01:13

wa#4 for countless times, seek for kind help!
thanks

O(n+m) solution exists: extend <https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm> to keep not only the top of each set in the disjoint-set forest, but also the weight of the path till that top.

  u and v,which is the father node?

Anyone crash test#2

used RMQ using segment tree to find lca in log(n)
total time complexity O(n+q*(lgn)) = O(q*lgn)

solved. thanks

Edited by author 26.12.2013 09:01

On Java I reccomend to use ArrayList instead Stack. It saved me about 0.4 sec.

Edited by author 10.03.2017 00:06

can anyone tell me what is the 'problem' with test #5, because I get stack overflow, although I don't declare any local variables in my recursive function (I use a vector to simulate the stack)

If anyone know hint or test case for test#13

plz, help me! why i get crash(access violation).
// LCA (least common ancestor) offline by using interval tree in O(logN)
// Solution by Serekov Abzal

#pragma comment(linker, "/STACK:16777216")

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>

using namespace std;
int ADD = 65536;
int inf = 9999999;
vector <vector <pair<int, int> > > graph;
vector <bool> b(50001, false);
vector <int> h(50001, 0);
vector <int> order;
vector <int> d(50001, 0);
vector <int> first(50001, -1);
pair <int, int> tree[2 * 65536 + 1];
int n, root = 0;
void init_graph()
{
    scanf("%d", &n);
    graph.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
};
void dfs(int v, int p)
{
    b[v] = true;
    h[v] = p;
    order.push_back(v);
    for (int i = 0; i < graph[v].size(); i++)
        if (!b[graph[v][i].first])
        {
            dfs(graph[v][i].first, p + 1);
            order.push_back(v);
        }
};
void bfs(int v)
{
    queue <int> Q;
    Q.push(v);
    while (!Q.empty())
    {
        int u = Q.front();
        b[u] = true;
        for (int i = 0; i < graph[u].size(); i++)
            if (!b[graph[u][i].first])
            {
                d[graph[u][i].first] = d[u] + graph[u][i].second;
                Q.push(graph[u][i].first);
            }
        Q.pop();
    }
};
void prepare()
{
    h[root] = 0;
    dfs(root, 0);
    for (int i = 0; i < order.size(); i++)
        if (first[order[i]] == -1)
            first[order[i]] = i;
    for (int i = 0; i < n; i++) b[i] = false;
    d[root] = 0;
    bfs(root);
};
int minimum(int u, int v)
{
    int l = u, r = v, ans = inf, ver = inf;
    while (l <= r)
    {
        if (l % 2 == 1)
        {
            if (tree[l].second < ans)
            {
                ans = tree[l].second;
                ver = tree[l].first;
            }
            l++;
        };
        if (r % 2 == 0)
        {
            if (tree[r].second < ans)
            {
                ans = tree[r].second;
                ver = tree[r].first;
            }
            --r;
        }
        l/=2; r/=2;
    }
    return ver;
};
int lca(int u, int v)
{
    int l = first[u] + ADD, r = first[v] + ADD;
    return minimum(l, r);
};
void init_zaprosi()
{
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int ans = d[u] + d[v] - 2 * d[lca(u, v)];
        printf("%d\n", ans);
    }
};
void tree_build()
{
    for (int i = 0; i <= 2 * ADD; i++)
    tree[i] = make_pair(-1, inf);

    for (int i = ADD; i < ADD + order.size(); i++)
    {
        tree[i].first = order[i - ADD];
        tree[i].second = h[order[i - ADD]];
    }
    for (int i = ADD - 1; i > 0; i--)
    {
        if (tree[2 * i].first == -1 || tree[2 * i + 1].first == -1)
        {
            if (!(tree[2 * i].first == -1 && tree[2 * i + 1].first == -1))
            {
                if (tree[2 * i].first == -1) tree[i] = tree[2 * i + 1]; else tree[i] = tree[2 * i];
            }
        }
        else
        {
            if (tree[2 * i].second < tree[2 * i + 1].second) tree[i] = tree[2 * i];    else tree[i] = tree[2 * i + 1];
        }
    }
};
int main()
{
    init_graph();
    prepare();
    tree_build();
    init_zaprosi();
    return 0;
}

Is a root node for the tree?

- New tests added
- Time limit is set to 1 sec (was 2 sec)
78 authors have lost AC after rejudge.

What can it be, please? WA2

Anyone knows what's test 9 ? I'm getting WA but my algo work in all cases I test.

I'm using Floyd-Warshall algorithm, and my program correctcly passes different tests, but i have WA1. Why?