题目链接：https://vijos.org/p/1460
http://oj.fjaxyz.com:3389/problem.php?id=223
我不禁开始怀疑，这，真的是最近公共祖先的题吗，我是从一个讲解LCA的博客里找到这道题的，然后我就乖乖的用了可爱的LCA倍增，然后我就更加愉快的TLE了。
【思路】
判断u,v 的最近公共祖先是不是u，如果是，就加上这条路线。。。
判断u,v的最近公共祖先是不是u，TLE的代码是用倍增算法做的这个，但是啊，其实我们换一种说法就是判断u是不是v的祖先
那么这就简单了，想想LCA的离线做法tarjan，里面的dfn数组，储存的是i点的dfs序号，然后实质上其实是前序遍历序号
怎么判断u是v的祖先？刚刚才提到前序遍历，那我想想后序遍历，前序是根左右，后序是左右根，那么意思就是根在前序是比叶节点序号小，在后序是比叶节点序号大
于是我们储存数组begn[] ed[]储存点的前序序号和后序序号，如果begn[u]<begn[v]&&ed[u]>ed[v]说明u是v的祖先
解决了这个问题，接下来就是求距离，我们储存数组dis表示点i到根节点的距离，
所以u,v距离就是dis[u]+dis[v]-2*dis[lca(u,v)]，由于这题满足条件是u为v的祖先，所以距离简化为dis[v]-dis[u]
LCA倍增算法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdlib>
#define maxn 10005
#define ll long long
using namespace std; struct node{
int u,v;ll w;int nxt;
}e[maxn]; int head[maxn],n,m,f[maxn][];
ll dis[maxn],ans;
int cnt,vis[maxn],dep[maxn]; int tot;
void adde(int u,int v,int w){
e[tot]=(node){u,v,w,head[u]};
head[u]=tot;tot++;
} void build(int u){
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].v;
if(!vis[v]){
f[v][]=u;
dis[v]=dis[u]+e[i].w;
dep[v]=dep[u]+;
vis[v]=;
build(v);
}
}
} void first(){
for(int j=;j<=;j++){
for(int i=;i<=n;i++){
f[i][j]=f[f[i][j-]][j-];
}
}
} int up(int x,int d){
for(int i=;i<=d;i++)
x=f[x][];
return x;
} int find(int x,int y){
if(dep[x]<dep[y])swap(x,y);
if(dep[x]!=dep[y]){
int dd=dep[x]-dep[y];
x=up(x,dd);
}
if(x==y){return x;}
for(int j=;j>=;j--){
if(f[x][j]!=f[y][j]){
x=f[x][j];y=f[y][j];
}
}
return f[x][];
} ll len(int u,int v){
return dis[v]-dis[u];
} int main(){
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);
}
build();
first();
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
int lca=find(u,v);
if(lca==u){ans+=len(u,v);cnt++;}
}
printf("%d\n%lld",cnt,ans);
}
倍增（TLE）
运用前序后序的dfs算法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdlib>
#define maxn 10005
using namespace std; struct node{
int u,v;long long w;int nxt;
}e[maxn]; int head[maxn],n,m;
int cnt,vis[maxn];
int begn[maxn],ed[maxn];
long long ans,dis[maxn]; int tot;
void adde(int u,int v,long long w){
e[tot]=(node){u,v,w,head[u]};
head[u]=tot;tot++;
} int num,hehe;
void build(int u){
num++;begn[u]=num;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].v;
if(!vis[v]){;
dis[v]=dis[u]+e[i].w;
vis[v]=;
build(v);
}
}
hehe++;ed[u]=hehe;
} int main(){
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
int u,v;long long w;
scanf("%d%d%lld",&u,&v,&w);
adde(u,v,w);
}
build();
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
if(begn[u]<=begn[v]&&ed[u]>=ed[v]){
ans+=dis[v]-dis[u];cnt++;
}
}
printf("%d\n%lld",cnt,ans);
}
AC于vijos
然后问题就来了，这个在vijos上AC的代码在meto code上还是WA了，我已经放弃了，因为meto code不提供错误数据也不告诉我错了几组，所以我最终还是没有在meto code上成功