#include <bits/stdc++.h>
using namespace std;
#define ll long long
using namespace std;
const int mod = 1e9+7;/// 998244353;
const int mxn = 8e4 +7;
const int N = 8e4 + 7 ;
int _,m,n,t,k,ans,cnt,lg;
int head[N] , far[N] , len[N] , vis[N] , a[mxn] ;
vector< pair<int,int> > q[N] ;
struct ${
int to , nx , w ;
}e[mxn*2];
int root(int x)
{
return x==far[x] ? x : far[x] = root(far[x]);
}
void add(int u,int v,int w)
{
e[cnt].to = v ;
e[cnt].w = w ;
e[cnt].nx = head[u] ;
head[u] = cnt++;
}
void tarjan(int u)
{
vis[u] = 1 ;
for(int i=head[u];~i;i=e[i].nx){
int v = e[i].to ;
if(!vis[v]){
len[v] = len[u] + e[i].w ;
tarjan(v);
far[v] = u ;
}
}
for(int i=0;i<q[u].size();i++){
int v = q[u][i].first , id = q[u][i].second ;
if(vis[v]==2){
int lca = root(v);
a[id] = min( a[id] , len[u]+len[v] - 2*len[lca] );
}
}
vis[u] = 2 ;
}
void init()
{
cnt = 0 ;
for(int i=0;i<=n;i++)
len[i] = 0 , far[i] = i , vis[i] = 0;
memset(head,-1,sizeof(head));
}
void solve()
{
for(cin>>t;t;t--){
cin>>n>>m;
init();
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
q[u].push_back( {v,i} );
q[v].push_back( {u,i} );
a[i] = 1<<30 ;
}
tarjan(1);
for(int i=1;i<=m;i++)
cout<<a[i]<<endl;
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 1e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 1e9+7 ;
using namespace std;
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
int p,t,n,m,k,si,res,cnt,to[mxn] , head[mxn] , nx[mxn],in[mxn] ,far[mxn];
int q[1024][1024] , ans[mxn] ;
bool vis[mxn];
void add(int u,int v){
to[cnt] = v ; nx[cnt] = head[u] ; head[u] = cnt++;
}
int Find(int x){return x==far[x] ? x : far[x] = Find(far[x]);}
void Tarjan(int u)
{
far[u] = u ;
for(int i=head[u];i!=-1;i=nx[i]){
int v = to[i] ;
Tarjan(v); far[v] = u ;
}
vis[u] = true ;
for(int i=1;i<=n;i++){
if(vis[i] && q[u][i])
ans[Find(i)] += q[u][i];
}
}
void init()
{
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
memset(ans,0,sizeof(ans));
memset(in,0,sizeof(in));
memset(q,0,sizeof(q));
cnt = 0 ;
}
void solve()
{
while(~scanf("%d",&n)){
init();
for(int i=1,u,v,m;i<=n;i++){
scanf("%d:(%d)",&u,&m);
while(m--){
scanf(" %d",&v);
add(u,v); in[v]++;
}
}
scanf(" %d",&m);
for(int i=1,u,v;i<=m;i++){
scanf(" (%d %d)",&u,&v);
q[u][v]++; q[v][u]++;
}
for(int i=1;i<=n;i++){
if(!in[i]) {
Tarjan(i) ; break;
}
}
for(int i=1;i<=n;i++){
if(ans[i]) printf("%d:%d\n",i,ans[i]);
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 1e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 1e9+7 ;
using namespace std;
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
int p,t,n,m,k,si,res,cnt;
int to[mxn] , head[mxn] , nx[mxn] ,in[mxn] ,far[mxn] , ans[mxn] , qto[mxn] , qhead[mxn] , dep[mxn];
bool vis[mxn] ;
struct ${
int u , v , w , nx ;
}e[mxn] , q[mxn];
int Find(int x) {return x==far[x]?x:far[x] = Find(far[x]) ;}
void add(int u,int v,int w){
e[cnt].v = v ; e[cnt].w = w ;e[cnt].nx = head[u] ; head[u] = cnt++;
}
void Add(int u,int v,int i){
q[res].v = v ; q[res].w = i; q[res].nx = qhead[u] ; qhead[u] = res++;
}
void init()
{
cnt = 0 ; res = 0 ;
memset(head,-1,sizeof(head));
memset(qhead,-1,sizeof(qhead));
}
void Tarjan(int u,int d)
{
far[u] = u ; vis[u] = true ;dep[u] = d ;
for(int i=head[u];i!=-1;i=e[i].nx){
int v = e[i].v , w = e[i].w;
if(!vis[v]){
Tarjan(v,d+w); far[v] = u ;
}
}
for(int i=qhead[u];i!=-1;i=q[i].nx){
int v = q[i].v , id = q[i].w ;
if(vis[v]){
ans[id] = dep[u] + dep[v] - 2*dep[Find(v)];
}
}
}
void solve()
{
rd(n) , rd(m) ; init(); char ch[5] ;
for(int i=1,u,v,w;i<n;i++){
rd(u) , rd(v) ,rd(w) ;scanf("%s",&ch);
add(u,v,w); add(v,u,w);
}
rd(k);
for(int i=1,u,v;i<=k;i++){
rd(u) , rd(v) ;
Add(u,v,i) ; Add(v,u,i);
}
Tarjan(1,0);
for(int i=1;i<=k;i++){
printf("%d\n",ans[i]);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e4+7 ;
#define ll long long
ll n,m,t,k,ans,cnt;
int to[mxn] , head[mxn] , st[30][mxn] , dep[mxn] , len[mxn] , far[mxn];
bool vis[mxn];
struct $
{
int to , w , nx ;
}e[mxn];
void init()
{
cnt = 0 ;
memset(vis,false,sizeof(vis));
memset(head,-1,sizeof(head));
memset(len,0,sizeof(len));
memset(dep,0,sizeof(dep));
memset(st,0,sizeof(st));
for(int i=1;i<=n;i++)
far[i] = i ;
}
void add(int u,int v,int w)
{
e[cnt].to = v ;
e[cnt].w = w ;
e[cnt].nx = head[u];
head[u] = cnt++;
}
int Find(int x)
{
return x==far[x] ? x:far[x] = Find(far[x]);
}
void merge(int u ,int v) /// 合并
{
int iu = Find(u) , iv = Find(v);
if(iv!=iu) far[iv] = iu ;
}
void ST()
{
for(int i=0;i<16;i++){
for(int j=1;j<=n;j++){
if(st[i][j]<0)
st[i+1][j] = -1 ;
else
st[i+1][j] = st[i][ st[i][j] ];
}
}
}
void dfs(int u,int pre) /// 搜索树
{
vis[u] = true;
for(int i=head[u] , v;~i;i=e[i].nx){
v = e[i].to ;
if(!vis[v]){
len[v] = len[u] + e[i].w ;
dep[v] = dep[u] + 1 ;
st[0][v] = u ;
dfs(v,u) ;
}
}
}
int lca(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
for(int i=0;i<16;i++){
if((dep[v]-dep[u])>>i&1)
v = st[i][v] ;
}
if(u==v) return u ;
for(int i=15;i>=0;i--){
if(st[i][u] != st[i][v]){
u = st[i][u] ;
v = st[i][v] ;
}
}
return st[0][v];
}
void solve()
{
while(cin>>n>>m>>k)
{
init(); /// 初始化
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
merge(u,v);
}
for(int i=1;i<=n;i++){ /// 建树
if(!vis[i]){
dfs(i,-1);
}
}
ST(); ///
for(int i=1,u,v;i<=k;i++){
cin>>u>>v;
int iu = Find(u);
int iv = Find(v);
if(iu==iv)
cout<< len[u]+len[v]-2*len[lca(u,v)] <<endl;
else
cout<<"Not connected\n";
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <bits/stdc++.h>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 2e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 1e9+7 ;
using namespace std;
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
ll p,t,n,m,k,si,cnt,to[mxn] , head[mxn] , f[mxn][30] , dep[mxn] , nx[mxn], res , mx ;
ll a[mxn];
void add(int u,int v)
{
to[cnt] = v ;
nx[cnt] = head[u] ;
head[u] = cnt++;
}
void init()
{
cnt = 0 ;
memset(head,-1,sizeof(head));
memset(f,-1,sizeof(f));
}
void dfs(int x,int pre,int d)
{
f[x][0] = pre ; dep[x] = d ;
for(int i=head[x],v;i!=-1;i=nx[i]){
v = to[i] ;
if(v!=pre) dfs(v,x,d+1);
}
}
void ST()
{
dfs(1,-1,0);
for(int j=0;(1<<(j+1))<=n;j++){
for(int i=1;i<=n;i++){
if(f[i][j]<0) f[i][j+1] = -1 ;
else f[i][j+1] = f[ f[i][j] ][j] ;
}
}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);/// 保持u深度小于v深度
int det = dep[v] - dep[u] ; /// 深度差
for(int i=20;i>=0;i--){
if((1<<i)&det) v = f[v][i] ;
}
if(u==v) return u;
for(int i=20;i>=0;i--){
if(f[u][i] != f[v][i]){
u = f[u][i] ; v = f[v][i] ;
}
}
return f[u][0];
}
void query(int u,int v,int k)
{
int lca = LCA(u,v);
if(dep[u]+dep[v]-2*dep[lca] + 1 < k){
puts("invalid request!");
return ;
}
vector<int>vi;vi.push_back(a[lca]);
while(u!=lca) vi.push_back(a[u]) , u = f[u][0];
while(v!=lca) vi.push_back(a[v]) , v = f[v][0];
sort(vi.begin(),vi.end());
printf("%d\n",vi[vi.size()-k]);
}
void solve()
{
rd(n) , rd(m) ;
for(int i=1;i<=n;i++) rd(a[i]);
init();
for(int i=1,u,v;i<n;i++){
rd(u) , rd(v) ;
add(u,v) ; add(v,u) ;
}
ST();
for(int i=1,u,v;i<=m;i++){
rd(k) , rd(u) , rd(v) ;
if(!k) a[u] = v ;
else query(u,v,k);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}
#include <bits/stdc++.h>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 5e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 1e9+7 ;
using namespace std;
typedef long long ll;
template <class T>
void rd(T &x){
x=0;T f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
x*=f;
}
ll p,t,n,m,k,si,cnt,to[mxn] , head[mxn] , f[mxn][30] , dep[mxn] , nx[mxn], res , mx ;
ll a[mxn];
void add(int u,int v)
{
to[cnt] = v ;
nx[cnt] = head[u] ;
head[u] = cnt++;
}
void init()
{
cnt = 0 ;
memset(head,-1,sizeof(head));
memset(f,-1,sizeof(f));
}
void dfs(int x,int pre,int d)
{
dep[x] = d ; f[x][0] = pre ;
for(int i=head[x] , v;i!=-1;i=nx[i]){
v = to[i] ;
if(v!=pre) dfs(v,x,d+1);
}
}
void ST()
{
dfs(1,-1,0);
for(int j=0;(1<<(j+1))<=n;j++){
for(int i=1;i<=n;i++){
if(f[i][j]<0) f[i][j+1] = -1 ;
else f[i][j+1] = f[ f[i][j] ][j];
}
}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
for(int i=20;i>=0;i--){
if(dep[f[v][i]]>=dep[u]) v = f[v][i];
}
if(u==v) return u;
for(int i=20;i>=0;i--){
if(f[v][i]!=f[u][i])
v=f[v][i] , u=f[u][i];
}
return f[v][0];
}
ll ksm(ll x,ll p)
{
ll ans = 1 ;
while(p){
if(p&1) ans =ans*x%mod;
x = x*x %mod;
p>>=1;
}
return ans;
}
void solve()
{
rd(n); init();
for(int i=1,u,v;i<n;i++){
rd(u) , rd(v) ;
add(u,v) ; add(v,u) ;
}
ST(); rd(k); ll ans = 0 , q = k;
while(k--){
int a,b,c,t;
rd(a) , rd(b) , rd(c) , rd(t) ;
int lca = dep[LCA(c,b)];
int len = dep[c]+2*(dep[b]-lca);
if(dep[a]<t && len<t) ans++;
}
printf("%d\n",ans*ksm(q,mod-2)%mod);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
}