Need help :))))

Can anybody tell me test 10?

you can use Binary Lifting,find lca of u and v
you find distance u with root of tree
the result=dis[a]+dis[b]-2*dis[lca(a,b)]

No clue as to what's wrong. Can anyone please give me a hint or what's the case?

What can it be?(tests or ideas, something pls)

passes

3
0 1 1
1 2 0
1
1 2

ans:
0

but still WA


Edited by author 20.04.2021 00:52

What can it be, please? WA2

5
0 1 1
0 2 1
1 3 1
1 4 1
2
3 2
4 3

ans:
3
2


5
1 0 1
2 0 1
3 1 1
4 1 1
2
2 3
4 3

ans:
3
2


3
2 1 1
0 2 1
3
0 0
0 1
1 1

ans:
0
2
0

5
0 1 1
0 2 2
1 3 3
1 4 1
2
2 3
4 3
6
4

ans:
6
4

8
0 1 1
0 2 1
2 3 1
3 4 1
0 5 1
5 6 1
6 7 1
6
7 7
1 4
4 4
4 3
3 4
7 0

ans:
0
4
0
1
1
3

5
0 1 1
1 2 1
3 0 1
0 4 1
4
0 4
4 0
0 2
2 0

ans:
1
1
2
2
Edited by author 17.04.2021 20:29



Edited by author 17.04.2021 20:50

Edited by author 20.04.2021 00:30

Edited by author 20.04.2021 00:41

Edited by author 20.04.2021 23:06

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)