Language: C++

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,q;
#define Maxn 100010
#define V 4000010
int root[Maxn<<1];
struct Node{
	int sum,cnt;
	int ls,rs;
}tree[V];
int all=0;
void Insert(int &k,int x,int l,int r,int pos,int ad1,int ad2){
	 k=++all;
	 tree[k]=tree[x];
	 tree[k].sum+=ad1;tree[k].cnt+=ad2;
	 if(l==r)return;
	 int mid=(l+r)>>1;
	 if(pos<=mid)Insert(tree[k].ls,tree[x].ls,l,mid,pos,ad1,ad2);
	 else Insert(tree[k].rs,tree[x].rs,mid+1,r,pos,ad1,ad2);
}
pair<int,int> Query(int k1,int k2,int l,int r,int L,int R){
	if(l==L&&r==R){
		pair<int,int> res;
		res.first=tree[k2].sum-tree[k1].sum;
		res.second=tree[k2].cnt-tree[k1].cnt;
		return res;
	}
	int mid=(l+r)>>1;
	if(R<=mid)return Query(tree[k1].ls,tree[k2].ls,l,mid,L,R);
	else if(mid<L)return Query(tree[k1].rs,tree[k2].rs,mid+1,r,L,R);
	else{
		pair<int,int> res1=Query(tree[k1].ls,tree[k2].ls,l,mid,L,mid);
		pair<int,int> res2=Query(tree[k1].rs,tree[k2].rs,mid+1,r,mid+1,R);
		return make_pair(res1.first+res2.first,res1.second+res2.second);
	}
}

int head[Maxn],v[Maxn<<1],w[Maxn<<1],nxt[Maxn<<1],tot=0;
int dis[Maxn],in[Maxn],out[Maxn],dfk=0;
int fa[Maxn][20];
inline void add_edge(int s,int e,int t){
	tot++;v[tot]=e;nxt[tot]=head[s];w[tot]=t;head[s]=tot;
	tot++;v[tot]=s;nxt[tot]=head[e];w[tot]=t;head[e]=tot;
}

struct Edge{
	int s,e,t1,t2;
	bool operator <(const Edge &z)const{return t1<z.t1;}
}edge[Maxn];
int end[Maxn];

int depth[Maxn];
inline void go_up(int &k,int d){
	for(int i=19;i>=0;--i)
	    if(d&(1<<i))k=fa[k][i];
}
inline int LCA(int a,int b){
	if(depth[a]>depth[b])go_up(a,depth[a]-depth[b]);
	if(depth[a]<depth[b])go_up(b,depth[b]-depth[a]);
	if(a==b)return a;
	for(register int i=19;i>=0;--i)
	    if(fa[a][i]!=fa[b][i]){
			a=fa[a][i];
			b=fa[b][i];
	    }
	return fa[a][0]; 
}

void dfs(int u,int f){
	depth[u]=depth[f]+1;
	fa[u][0]=f;
	for(register int i=1;i<=19;++i)fa[u][i]=fa[fa[u][i-1]][i-1]; 
	in[u]=++dfk;
	for(int i=head[u];i;i=nxt[i])
	    if(v[i]^f){
			dis[v[i]]=dis[u]+w[i];
			dfs(v[i],u);
	    }
	out[u]=dfk;
}

inline void rd(int &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar(); 
	}
}

int main(){
	scanf("%d%d",&n,&q);
	for(register int i=1;i<n;++i){
		rd(edge[i].s);rd(edge[i].e);rd(edge[i].t1);rd(edge[i].t2);
		add_edge(edge[i].s,edge[i].e,edge[i].t2);
	}
	dfs(1,0);
	sort(edge+1,edge+n);
//	puts("fuck");
	for(int i=1;i<n;++i){
		int at;
		if(in[edge[i].s]<in[edge[i].e])at=edge[i].e;
		else at=edge[i].s;
		Insert(root[i*2-1],root[i*2-2],1,n,in[at],edge[i].t2,1);
		if(out[at]!=n)Insert(root[i*2],root[i*2-1],1,n,out[at]+1,-edge[i].t2,-1);
		else Insert(root[i*2],root[i*2-1],1,n,1,0,0);
		end[edge[i].t1]=i*2;
	}
	for(register int i=1;i<=n-1;++i)
	    if(!end[i])end[i]=end[i-1];
	int x,y,s,e;
	 for(register int i=1;i<=q;++i){
			rd(x);rd(y);rd(s);rd(e);
			int lca=LCA(s,e);
			int res=dis[s]+dis[e]-dis[lca];
		//	cout<<end[x]<<endl;
			pair<int,int> tmp1=Query(root[end[x-1]],root[end[x]],1,n,1,in[s]);
		//	puts("fuck");
			pair<int,int> tmp2=Query(root[end[x-1]],root[end[x]],1,n,1,in[e]);
		//	puts("fuck");
			pair<int,int> tmp3=Query(root[end[x-1]],root[end[x]],1,n,1,in[lca]);
		//	puts("fuck");
			//cout<<"res "<<res<<endl; 
			res-=tmp1.first;
			res-=tmp2.first;
			res+=tmp3.first;
		//	cout<<"res "<<res<<endl;
			res+=y*(tmp1.second+tmp2.second-tmp3.second);
			printf("%d\n",res);
	 }
	 return 0;
}

Compiler output:
a.cc: In function 'int LCA(int, int)':
a.cc:65:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   65 |         for(register int i=19;i>=0;--i)
      |                          ^
a.cc: In function 'void dfs(int, int)':
a.cc:76:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   76 |         for(register int i=1;i<=19;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
      |                          ^
a.cc: In function 'int main()':
a.cc:97:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   97 |         for(register int i=1;i<n;++i){
      |                          ^
a.cc:111:17: error: reference to 'end' is ambiguous
  111 |                 end[edge[i].t1]=i*2;
      |                 ^~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115 |   template<typename _Tp> _Tp* end(valarray<_Tp>&) noexcept;
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:106:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  106 |     end(_Tp (&__arr)[_Nm]) noexcept
      |     ^~~
/usr/include/c++/14/bits/range_access.h:85:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   85 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/bits/range_access.h:74:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   74 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
In file included from /usr/include/c++/14/bits/range_access.h:36:
/usr/include/c++/14/initializer_list:99:5: note:                 'template<class _Tp> constexpr const _Tp* std::end(initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
a.cc:54:5: note:                 'int end [100010]'
   54 | int end[Maxn];
      |     ^~~
a.cc:113:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  113 |         for(register int i=1;i<=n-1;++i)
      |                          ^
a.cc:114:17: error: reference to 'end' is ambiguous
  114 |             if(!end[i])end[i]=end[i-1];
      |                 ^~~
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115 |   template<typename _Tp> _Tp* end(valarray<_Tp>&) noexcept;
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:106:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  106 |     end(_Tp (&__arr)[_Nm]) noexcept
      |     ^~~
/usr/include/c++/14/bits/range_access.h:85:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   85 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/bits/range_access.h:74:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   74 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/initializer_list:99:5: note:                 'template<class _Tp> constexpr const _Tp* std::end(initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
a.cc:54:5: note:                 'int end [100010]'
   54 | int end[Maxn];
      |     ^~~
a.cc:114:24: error: reference to 'end' is ambiguous
  114 |             if(!end[i])end[i]=end[i-1];
      |                        ^~~
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115 |   template<typename _Tp> _Tp* end(valarray<_Tp>&) noexcept;
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:106:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  106 |     end(_Tp (&__arr)[_Nm]) noexcept
      |     ^~~
/usr/include/c++/14/bits/range_access.h:85:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   85 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/bits/range_access.h:74:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   74 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/initializer_list:99:5: note:                 'template<class _Tp> constexpr const _Tp* std::end(initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
a.cc:54:5: note:                 'int end [100010]'
   54 | int end[Maxn];
      |     ^~~
a.cc:114:31: error: reference to 'end' is ambiguous
  114 |             if(!end[i])end[i]=end[i-1];
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115 |   template<typename _Tp> _Tp* end(valarray<_Tp>&) noexcept;
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:106:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  106 |     end(_Tp (&__arr)[_Nm]) noexcept
      |     ^~~
/usr/include/c++/14/bits/range_access.h:85:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   85 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/bits/range_access.h:74:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   74 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/initializer_list:99:5: note:                 'template<class _Tp> constexpr const _Tp* std::end(initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
a.cc:54:5: note:                 'int end [100010]'
   54 | int end[Maxn];
      |     ^~~
a.cc:116:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  116 |          for(register int i=1;i<=q;++i){
      |                           ^
a.cc:121:55: error: reference to 'end' is ambiguous
  121 |                         pair<int,int> tmp1=Query(root[end[x-1]],root[end[x]],1,n,1,in[s]);
      |                                                       ^~~
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115 |   template<typename _Tp> _Tp* end(valarray<_Tp>&) noexcept;
      |                               ^~~
/usr/include/c++/14/bits/range_access.h:106:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  106 |     end(_Tp (&__arr)[_Nm]) noexcept
      |     ^~~
/usr/include/c++/14/bits/range_access.h:85:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   85 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/bits/range_access.h:74:5: note:                 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   74 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/14/initializer_list:99:5: note:                 'template<class _Tp> constexpr const _Tp* std::end(initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
a.cc:54:5: note:                 'int end [100010]'
   54 | int end[Maxn];
      |     ^~~
a.cc:121:70: error: reference to 'end' is ambiguous
  121 |                         pair<int,int> tmp1=Query(root[end[x-1]],root[end[x]],1,n,1,in[s]);
      |                                                                      ^~~
/usr/include/c++/14/bits/range_access.h:116:37: note: candidates are: 'template<class _Tp> const _Tp* std::end(const valarray<_Tp>&)'
  116 |   template<typename _Tp> const _Tp* end(const valarray<_Tp>&) noexcept;
      |                                     ^~~
/usr/include/c++/14/bits/range_access.h:115:31: note:                 'template<class _Tp> _Tp* std::end(valarray<_Tp>&)'
  115