Tarjan
#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......
");
#define pfd(x) printf("%d
",x)
#define pfl(x) printf("%lld
",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 4e4+10;
const int M = 2e2+10;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
int n,q;//n个顶点 q次询问
int lca[maxn];//lca[i]表示第i个询问的结果 祖先
int dist[maxn];//dist[i]表示i到根节点的距离
//对树建图
int head[maxn];
int cnt;
struct node{
int v,nxt,w;
}edge[maxn*2];
//对询问建图
int headq[maxn];
int cntq;
struct Node{
int u,v;//起点和终点
int nxt;//同起点的下一个询问的位置
int id;//记下是第几次询问
}query[M*2];
bool vis[maxn];//访问标志
//树加边
void addEdge(int u, int v, int w){
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
//询问加边
void addQ(int u, int v, int idx){
query[cntq].u = u;
query[cntq].v = v;
query[cntq].nxt = headq[u];
query[cntq].id = idx;
headq[u] = cntq++;
}
//并查集基本操作
int fa[maxn];
void init(){
rep(i,1,n+5){
fa[i] = i;
vis[i] = 0;
head[i] = 0;
headq[i] = 0;
}
dist[1] = 0;
cnt = 1;
cntq = 1;
}
int find(int x){
if(x != fa[x]){
return fa[x] = find(fa[x]);
}
return x;
}
void merge(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx != fy) fa[fy] = fx;
}
//tarjan
void tarjan(int u){
vis[u] = 1;
for(int i=head[u]; i; i=edge[i].nxt){
int v = edge[i].v;
int w = edge[i].w;
if(!vis[v]){
dist[v] = w + dist[u];//沿途求出每个结点到root的距离 root=1
tarjan(v);
merge(u , v);//v回溯，u是v的父亲
}
}
//u结束 u回溯，把与u有查询关系的能更新的都更新了
for(int i=headq[u]; i; i=query[i].nxt){
int v = query[i].v;
if(vis[v]) lca[query[i].id] = find(v);
}
}
int t;
int main(){
sc(t);
while(t--){
sc2(n,q);
init();//初始化不能忘记
int u,v,w;
rep(i,1,n-1){
sc2(u,v);
sc(w);
addEdge(u,v,w);
addEdge(v,u,w);
}
rep(i,1,q){
sc2(u,v);
addQ(u,v,i);
addQ(v,u,i);
}
tarjan(1);
//事实上可以只选出奇数或者偶数次序的询问因为 （1,2） （3,4） （5,6）...括号内是等价的
rep(i,1,cntq-1){
i++;
u = query[i].u;
v = query[i].v;
int idx = query[i].id;
pfd(dist[u]+dist[v]-2*dist[lca[idx]]);
}
}
return 0;
}
//LCA 倍增 大家一起跳跳跳
#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......
");
#define pfd(x) printf("%d
",x)
#define pfl(x) printf("%lld
",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 1e4+10;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
int t,n;
vector<int> G[maxn];
int in[maxn];//记录入度
int s,e,lca;
int depth[maxn];//记录每个结点的深度 根节点深度为0
int fa[maxn][20];//fa[i][j]表示i结点向上爬 2^j是哪个结点
//预处理出每个结点的深度和其直接父节点
void dfs(int u, int pre, int d){
fa[u][0] = pre;//向上一个当然是直接父节点 pre
depth[u] = d;//深度
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(v != pre){
dfs(v , u, d+1);
}
}
}
//倍增预处理出fa数组
void init(){
//有点区间DP的意思
for(int j=0; (1<<(j+1))<n; j++){
for(int i=1; i<=n; i++){
if(fa[i][j] < 0) fa[i][j+1] = -1;
else fa[i][j+1] = fa[fa[i][j]][j];
}
}
}
//给定俩个结点在线求其LCA
int LCA(int u, int v){
//保证v是较深的点
if(depth[u] > depth[v]) swap(u , v);
int temp = depth[v] - depth[u];//深度差
//先把v调到与u等高处
for(int i=0; (1<<i)<=temp; i++){
if((1<<i) & temp) v = fa[v][i];
}
if(u==v) return u;
//然后两个人比翼双飞
for(int i=(int)(log(1.0*n)/log(2.0)); i >= 0; i--){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
int main(){
sc(t);
int u,v;
while(t--){
sc(n);
rep(i , 1, n){
G[i].clear();
in[i] = 0;
}
rep(i , 1, n-1){
sc2(u,v);
G[u].push_back(v);
G[v].push_back(u);
in[v]++;
}
sc2(s,e);
int root;
rep(i , 1, n) if(in[i] == 0) root = i; //找到树根节点
dfs(root, -1, 0);
init();
pfd(LCA(s,e));
}
return 0;
}
//RMQ 把LCA转化为求区间深度最值
#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......
");
#define pfd(x) printf("%d
",x)
#define pfl(x) printf("%lld
",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 1e4+10;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
int n;
vector<int> G[maxn];//存树
int s,e;
int depth[2*maxn];///存结点深度
int order[2*maxn];//存储树的dfs序列
int dp[2*maxn][20];//存以i为起点的长度为2^j的区间最大值在dfs序列所处的位置
int first[maxn];//存储结点i第一次被访问到时在dfs序列中的位置
int cnt;//记数 dfs序列
bool vis[maxn];//访问标记
int in[maxn];
void init(){
rep(i,1,n){
G[i].clear();
vis[i] = 0;
in[i] = 0;
}
cnt = 0;
}
void dfs(int u, int d){
vis[u] = 1;
order[++cnt] = u;
depth[cnt] = d;
first[u] = cnt;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i];
if(!vis[v]){
dfs(v,d+1);
order[++cnt] = u;
depth[cnt] = d;
}
}
}
void ST(int n){
for(int i=1; i<=n; i++) dp[i][0] = i;
int k = (int)(log2(n*1.0));
for(int j=1; j<=k; j++)
for(int i=1; i+(1<<j)-1<=n; i++){
int a = dp[i][j-1];
int b = dp[i+(1<<(j-1))][j-1];
if(depth[a] < depth[b]) dp[i][j] = a;
else dp[i][j] = b;
}
}
int RMQ(int l , int r){
int k = (int)(log2(1.0*r - l + 1));
int a = dp[l][k];
int b = dp[r - (1<<k) + 1][k];
if(depth[a] < depth[b]) return a;
else return b;
}
int LCA(int x, int y){
//先找出x ,y第一次出现的位置
int l = first[x];
int r = first[y];
if(l > r) swap(l , r);//注意左边小于右边
//在[l,r]内寻找深度最大的位置
int pos = RMQ(l , r);
return order[pos];
}
int t;
int main(){
sc(t);
int u,v;
while(t--){
sc(n);
init();
rep(i , 1, n-1){
sc2(u,v);
G[u].push_back(v);
//G[v].push_back(u);
in[v]++;
}
sc2(s,e);
int root;
rep(i , 1, n) if(in[i] == 0) root = i; //找到树根节点
dfs(root , 1);
ST(2*n-1);
pfd(LCA(s,e));
}
return 0;
}