****Super Maximum Cost Queries

Super Maximum Cost Queries

Victoria has a tree, T$T$, consisting of N$N$ nodes numbered from 1$1$ to N$N$. Each edge from node Ui$U_i$ to Vi$V_i$ in tree T$T$ has an integer weight, Wi$W_i$.

Let's define the cost, C$C$, of a path from some node X$X$ to some other node Y$Y$ as the maximum weight (W$W$) for any edge in the unique path from node X$X$ to node Y$Y$.

Victoria wants your help processing Q$Q$ queries on tree T$T$, where each query contains 2$2$ integers, L$L$ and R$R$, such that L≤R$L\le R$. For each query, she wants to print the number of different paths in T$T$ that have a cost, C$C$, in the inclusive range [L,R]$[L,R]$.

It should be noted that path from some node X$X$ to some other node Y$Y$ is considered same as path from node Y$Y$ to X$X$ i.e {X,Y}$\{X,Y\}$ is same as {Y,X}$\{Y,X\}$.

Input Format

The first line contains 2$2$ space-separated integers, N$N$ (the number of nodes) and Q$Q$ (the number of queries), respectively. 
Each of the N−1$N-1$ subsequent lines contain 3$3$ space-separated integers, U$U$, V$V$, and W$W$, respectively, describing a bidirectional road between nodes U$U$ and V$V$ which has weight W$W$. 
The Q$Q$ subsequent lines each contain 2$2$ space-separated integers denoting L$L$ and R$R$.

Constraints

• 1≤N,Q≤105$1\le N,Q\le {10}^5$
• 1≤U,V≤N$1\le U,V\le N$
• 1≤W≤109$1\le W\le {10}^9$
• 1≤L≤R≤109$1\le L\le R\le {10}^9$

Scoring

• 1≤N,Q≤103$1\le N,Q\le {10}^3$ for 30%$30\mathrm{\%}$ of the test data.
• 1≤N,Q≤105$1\le N,Q\le {10}^5$ for 100%$100\mathrm{\%}$ of the test data.

Output Format

For each of the Q$Q$ queries, print the number of paths in T$T$ having cost C$C$ in the inclusive range [L,R]$[L,R]$ on a new line.

Sample Input

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

Sample Output

1
3
5
5
10

Explanation

Q1$Q_1$: {3,4}$\{3,4\}$ 
Q2$Q_2$: {1,3},{3,4},{1,4}$\{1,3\},\{3,4\},\{1,4\}$ 
Q3$Q_3$: {1,4},{1,2},{2,4},{1,3},{2,3}$\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 
Q4$Q_4$: {1,4},{1,2},{2,4},{1,3},{2,3}$\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 
...etc.

--------------------------------------------EDITORIAL---------------------------------------------

I HAVE SOLVED  A PROBLEM EARLIER WHICH IS SIMILAR TO THIS PROBLEM 

http://gautamlca.blogspot.in/2016/04/1162-min-max-roads_17.html

IN THIS PROBLEM WE NEDD TO FIND ALL  PATHS IN WHICH MAXIMUM IS IN THE RANGE OF L TO R ,

SINCE  SO IF WE GO THROUGH THE APPROACH OF ABOVE PROBLEM THAN WE NEED TO FIND MAXIMUM  OF  ALL  PATHS , ie B/W ALL PAIR OF NODES , SO THE COMPLEXITY WILL  BE  O(N^2LOG(N)) 

WHICH WILL  ONLY PASS FEW SMALL TEST CASE , SO WE HAVE TO APPROACH THIS PROBLEM IN A DIFFERENT WAY 

 THIS PROBLEM CAN BE SOLVED USING DSU , SORT THE EDGE ACCORDING TO WEIGHT ,

AND QUERIES ACCORDING TO R VALUE FIRST ,,

SEE THIS EDITORIAL ......

Let's solve this problem for a single (L, R) pair. Then we'll extend it to solve multiple queries efficiently.

Put only those edges i$i$ whose weight Wi≤R$W_i\le R$ is in the tree T$T$. Note that the tree T$T$ might be decomposed into a number of components. Now calculate the number of paths in tree T$T$. This easily be computed if you know the size of each component.

Say if there are X$X$ components where ith$i^{th}$ component has size sizei$siz{e}_i$, then the number of paths in tree T$T$is given by:

∑1≤i≤Xsizei×(sizei−1)2$$\sum _{1\le i\le X}\frac{siz{e}_i\times (siz{e}_i-1)}{2}$$

Note that above expression gives the count of all paths whose cost (C$C$) is ≤R$\le R$, as we have only those edges in the tree T$T$ whose weight Wi≤R$W_i\le R$.

Now calculate the same expression by putting all the edges whose weight Wi<L$W_i<L$ in tree T$T$ and subtract it from the previous count to get the number of paths whose value lie in the closed interval [L,R]$[L,R]$.

The above idea works in O(N)$O(N)$ time per query. This gives us an overall complexity of O(Q×N)$O(Q\times N)$, which will surely time out.

How to use above idea to answer queries efficiently?

• Sort all the given edges according to their weight (W$W$).
• One by one, add them to the tree while maintaining the number of paths in the tree's current state. This can be done using a Disjoint Set Union. This allows us to maintain the number of paths whose value is W$W$ for each distinct weight.
  

To handle queries, we just need to perform a binary search over the sorted array of weights to find if the interval lies in the range [L, R], and the sum of paths corresponding to the interval can be found by maintaining prefix sums.

Please have a look at author's solution to understand the explanation better.

------------------------------------------------CODE-----------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

vector<pair<pair<lli,lli> ,lli > > v,qry;

vector<pair<pair<lli,lli>,lli> > vv;

vector<pair<lli,lli> > fs;

lli ans[1000000];

lli parrent[1000000];

lli rankk[1000000];

map<lli,lli> ma; 

bool comp(pair<pair<lli,lli>,lli >p1 , pair<pair<lli,lli>,lli > p2)

 {

  if(p1.first.second<=p2.first.second) return true;

  return false;

 }

lli  find(lli a)

  {

    if(parrent[a]!=parrent[parrent[a]])

     {

      parrent[a]=find(parrent[a]);

     }

     return parrent[a];

 }

 void merge(lli a,lli b)

  {

   lli pa=find(a);

   lli pb=find(b);

   if(rankk[a]>rankk[b])

      {

      parrent[b]=a;

      rankk[a]+=rankk[b];

      rankk[b]=0;

      return ;

  }

  else

    { 

        parrent[a]=b;

  rankk[b]+=rankk[a];

  rankk[a]=0;

  }

  }

int main()

{

//freopen("abc.txt","w",stdout);

fs.push_back({0,0});

lli last=0;

   lli n,m;

   cin>>n>>m;

   for(lli i=0;i<=n+10;i++)

   {

     parrent[i]=i;

     rankk[i]=1;

   }

   for(lli i=0;i<n-1;i++)

        {

    lli a,b,c;

     cin>>a>>b>>c;

     v.push_back({{c,a},b});

}

    for(lli i=0;i<m;i++)

     {

   lli a,b;

   cin>>a>>b;

   qry.push_back({{a,b},i});

}

 

sort(v.begin(),v.end());

sort(qry.begin(),qry.end(),comp);

lli lastid=0;

lli lastval=v[0].first.first;

for(lli i=0;i<m;i++)

 {

  lli l=qry[i].first.first;

  lli r=qry[i].first.second;

  lli id=qry[i].second;

 

  if(lastval<=r)

     {

      while(lastid<n-1 && v[lastid].first.first<=r)

        {

        

        lli ll=v[lastid].first.second;

        lli rr=v[lastid].second;

 

        lli fl=find(ll);

              lli fr=find(rr); 

                 lli  len=rankk[fl]*rankk[fr];

                 merge(fl,fr);

                 lli upd=len;

              fs.push_back({fs[last].first+upd,v[lastid].first.first});

           

              last++;

              lastid++;

                 lastval=v[lastid].first.first;

  }

     }

  

// binary search ON THE  SECOND PARAMETER OF FS TO FIX LFFT END 

// FOR THE CURRENT QUERY , RIGHT END  WILL BE TILL LAST UPDATED 

// INDEX LAST .. 

// LEFT END WILL BE AT FS[LEFT]=L OR JUST LAST UPDATED VALUE < L

  lli lefft=0;lli riight=last;

  lli f=0;

  lli idx=0;

  while(lefft<=riight)

   {

    if(f==1) break;

      if(lefft==riight)

       {

    f=1;

}

lli mid=(lefft+riight)/2;

if(fs[mid].second<l)

{

 idx=max(idx,mid);

lefft=mid+1;

}

else

{

riight=mid;

}

}

 ans[id]=fs[last].first-fs[idx].first;

 }

for(lli i=0;i<m;i++) cout<<ans[i]<<endl;

}

---------------------------LCA CODE-------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef int lli;

vector<pair<pair<int,int> ,int> > v;

int dp_max[100010][25];

int dp_min[100010][25];

int dp_par[100010][25];

list<pair<int,int> > li[100010];

int lev[100010];

#define mp make_pair

int dfs(int start,int par,int l)

 {

  // cout<<" start "<<start<<endl;

  lev[start]=l;

  list<pair<int,int> >:: iterator it;

  for(it=li[start].begin();it!=li[start].end();it++)

    {

     if(it->first!=par)

      {

      /// cout<<" par of "<<it->first<<" is "<<start<<endl;

       lev[it->first]=l+1;

        dp_par[it->first][0]=start;

        dp_max[it->first][0]=it->second;

        //dp_min[it->first][0]=it->second;

        dfs(it->first,start,l+1);

   }

   }

   return 0;

 }

 int binary_rais(int a,int b)// return lca of a,b

 {

   if(lev[a]<lev[b]) swap(a,b);

   int lg;

   for(lg=1;(1<<lg)<=lev[a];lg++);

   lg--;

     for(int i=lg;i>=0;i--)

      {

        if(lev[a]-(1<<i)>=lev[b])

         {

            a=dp_par[a][i];//   moving a upward

          }

      }

   if(a==b) return a;

  

   else

   {

    for(int i=lg;i>=0;i--)

    {

     if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])//  moving botha and b up

      {

        a=dp_par[a][i];

        b=dp_par[b][i];

      }

    }

    return dp_par[a][0];

   }

 }

 int maximum(int a,int b,int par)

  {

   if(lev[a]<lev[b]) swap(a,b);

   int lg;

   for(lg=1;(1<<lg)<=lev[a];lg++);

   lg--;

   int ans=-1;

     for(int i=lg;i>=0;i--)

      {

        if(lev[a]-(1<<i)>=lev[b])

         {

           if(ans<dp_max[a][i])

             ans=dp_max[a][i];

            a=dp_par[a][i];//   moving a upward

          }

      }

     // cout<<" after same base ans "<<ans<<endl;

   if(a==b)

   {

     return ans;

   }

  

   else

   {

    for(int i=lg;i>=0;i--)

    {

     if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])//  moving botha and b up

      {

         ans=max(ans,dp_max[a][i]);

         ans=max(ans,dp_max[b][i]);

        a=dp_par[a][i];

        b=dp_par[b][i];

      }

    }

    return max(ans,max(dp_max[a][0],dp_max[b][0]));

   }

  }

  

int main()

{

        memset(dp_max,-1,sizeof dp_max);

        memset(dp_par,-1,sizeof dp_par);

     memset(lev,0,sizeof lev);

   

  

   

  

        int n,q;

        scanf("%d %d ",&n,&q);

       

    for(int i=0;i<n-1;i++)

     {

      int a,b,c;

         scanf("%d %d %d",&a,&b,&c);

         li[a].push_back({b,c});

         li[b].push_back({a,c});

         }

    

     dp_par[1][0]=0;

     dp_max[1][0]=0;

     dp_min[1][0]=0;

    

     dfs(1,0,1);

     

     for(int height=1;height<25;height++)

      {

        for(int i=1;i<=n;i++)

         {

           if(dp_par[i][height-1]!=-1)

           dp_par[i][height]=dp_par[dp_par[i][height-1]][height-1];

         }

      }

     

      for(int height=1;height<25;height++)

      {

        for(int i=1;i<=n;i++)

         {

           if(dp_par[i][height-1]!=-1)

           {

            dp_max[i][height]=max(dp_max[dp_par[i][height-1]][height-1],dp_max[i][height-1]);

            // dp_min[i][height]=min(dp_min[dp_par[i][height-1]][height-1],dp_min[i][height-1]);

  }

         

      }

      }

     vector<int>   v;

     for(int  i=1;i<=n;i++)

      {

      for(int j=i+1;j<=n;j++)

       {

         

  int par=binary_rais(i,j);

 // cout<<" par of "<<i<<" "<<j<<" is "<<par<<endl;

   lli  maxi=maximum(i,j,par);

 //   cout<<" i "<<i<<" j "<<j<<" maxi "<<maxi<<endl;

   v.push_back(maxi);

          //printf("%d %d\n",minimum(a,b,par),);

}

 }

  sort(v.begin(),v.end());    

     while(q--)

      {

        lli  a,b;

         scanf("%d %d",&a,&b);

         vector<int>:: iterator it;

            it=lower_bound(v.begin(),v.end(),a);

            lli count1=it-v.begin()+1;

            if(*it>=a) count1--;

            it=lower_bound(v.begin(),v.end(),b+1);

            if(it==v.end() || *it>b) it--;

              lli count2=it-v.begin()+1;

                cout<<count2-count1<<endl;

            

            

    }

    return 0;

}