找一点使这一点到三个点有最短距离 枚举三个两两LCA即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define inf 999999999
using namespace std;
int n,q,cnt;
int deep[500001],head[500001],fa[500001][20];
bool vis[500001];
struct data{
int to,next;
}e[1000001];
void ins(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void insert(int u,int v)
{
ins(u,v);
ins(v,u);
}
void dfs(int x)
{
vis[x]=1;
for(int i=1;i<=18;i++)
{
if(deep[x]<(1<<i))break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
deep[e[i].to]=deep[x]+1;
fa[e[i].to][0]=x;
dfs(e[i].to);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=18;i++)
if(t&(1<<i))x=fa[x][i];
for(int i=18;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{x=fa[x][i];y=fa[y][i];}
if(x==y)return x;
return fa[x][0];
}
int val(int x,int y,int z)
{
int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z);
int ans=inf,tmp,t;
int q1=lca(p1,z),q2=lca(p2,y),q3=lca(p3,x);
tmp=deep[x]+deep[y]-deep[p1]+deep[z]-2*deep[q1];
if(tmp<ans){ans=tmp;t=p1;}
tmp=deep[x]+deep[z]-deep[p2]+deep[y]-2*deep[q2];
if(tmp<ans){ans=tmp;t=p2;}
tmp=deep[y]+deep[z]-deep[p3]+deep[x]-2*deep[q3];
if(tmp<ans){ans=tmp;t=p3;}
printf("%d %d
",t,ans);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
}
dfs(1);
for(int i=1;i<=q;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
val(x,y,z);
}
return 0;
}
基础题 就求LCA 即可 到一个城市改变now值
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 60005
using namespace std;
int b[N],p[N],nt[N],deep[N],fa[N][25],vis[N];
int n,m;int num=0;
void insert(){
scanf("%d",&n);
int x,y;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
num++;
b[num]=y;
nt[num]=p[x];
p[x]=num;
num++;
b[num]=x;
nt[num]=p[y];
p[y]=num;
}
}
void dfs(int x){
vis[x]=1;
for(int i=1;i<=20;i++){
if(deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=p[x];i;i=nt[i]){
int v=b[i];
if(vis[v]) continue;
fa[v][0]=x;
deep[v]=deep[x]+1;
dfs(v);
}
}
int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=20;i++){
if(t&(1<<i)) x=fa[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
insert();
dfs(1);
scanf("%d",&m);
int now=1,to,ans=0;
for(int i=1;i<=m;i++){
scanf("%d",&to);
int t=lca(now,to);
int dis=deep[now]+deep[to]-2*deep[t];
//printf("t=%d %d to %d is %d
",t,now,to,dis);
ans+=dis;
now=to;
}
printf("%d",ans);
return 0;
}
同样的基础题 比上面的还简单
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 100005
#define N 100005
using namespace std;
int n,m;int num=0;
int b[M],w[M],nt[M],p[N];
int fa[M][20],d[M],val[N];
void insert(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
num++;
b[num]=y;
w[num]=z;
nt[num]=p[x];
p[x]=num;
num++;
b[num]=x;
w[num]=z;
nt[num]=p[y];
p[y]=num;
}
}
void dfs(int x){
for(int i=1;i<=20;i++){
if(d[x]<(1<<i))break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=p[x];i>0;i=nt[i]){
int v=b[i];
if(v==fa[x][0]) continue;//无向边 不走已经走过的父节点
fa[v][0]=x;
d[v]=d[x]+1;//求深度=父节点深度+1
val[v]=val[x]+w[i];//求与根结点距离 和深度类似
dfs(v);
}
}
int lca(int x,int y){//求LCA
int h;
if(d[x]<d[y]) swap(x,y);
for(h=0;(1<<h)<=d[x];h++);
h--;
for(int i=h;i>=0;i--){
if(d[x]-(1<<i)>=d[y])
x=fa[x][i];
}
if(x==y) return x;
for(int i=h;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
insert();
dfs(0);
scanf("%d",&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
printf("%d
",val[x]+val[y]-2*val[lca(x,y)]);
}
return 0;
}
记录深度数组和求LCA即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 10005
#define ll long long
using namespace std;
int n,m;
int b[N],p[N],nt[N],fa[N][21],d[N];
ll w[N];
ll val[N];
ll cnt,ans;
void insert(){
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=n-1;i++){
scanf("%d%d%d",&x,&y,&z);
b[i]=y;
w[i]=z;
nt[i]=p[x];
p[x]=i;
}
}
void dfs(int x){
for(int i=1;i<=20;i++){
if(d[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=p[x];i;i=nt[i]){
int v=b[i];
if(v==fa[x][0]) continue;
fa[v][0]=x;
d[v]=d[x]+1;
val[v]=val[x]+w[i];
dfs(v);
}
}
bool pdlca(int x,int y){
int t=d[x]-d[y];
for(int i=0;i<=20;i++)
if(t&(1<<i)) x=fa[x][i];
if(x==y) return 1;
else return 0;
}
int main(){
insert();
dfs(1);
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(d[v]<=d[u]) continue;
if(!pdlca(v,u)) continue;
cnt++;
ans+=val[v]-val[u];
}
printf("%lld
",cnt);
printf("%lld",ans);
return 0;
}
求树上三个点到某点
有最小距离和输出这个距离和方法是
会求两点最小距离 就会求三点距离=三个两两之间的最短距离相加再除2
(不明觉厉。。。)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
int b[N],p[N],nt[N],fa[N][30],val[N],w[N],deep[N];
int n,q,num=0;
void insert(){
num=0;
for(int i=1;i<=n-1;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
num++;
b[num]=y;
w[num]=z;
nt[num]=p[x];
p[x]=num;
num++;
b[num]=x;
w[num]=z;
nt[num]=p[y];
p[y]=num;
}
}
void dfs(int x,int h){
deep[x]=h;
for(int i=1;i<=26;i++){
if(deep[x]<(1<<i)) break;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=p[x];i;i=nt[i]){
int v=b[i];
if(v==fa[x][0]) continue;
fa[v][0]=x;
val[v]=val[x]+w[i];
dfs(v,h+1);
}
}
int lca(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=26;i++)
if(t&(1<<i)) x=fa[x][i];
if(x==y) return x;
for(int i=26;i>=0;i--){
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];y=fa[y][i];
}
}
return fa[x][0];
}
void clear(){
memset(fa,0,sizeof(fa));
memset(p,0,sizeof(p));
memset(val,0,sizeof(val));
}
int query(int x,int y){
int t=lca(x,y);
return val[x]+val[y]-2*val[t];
}
int deal(int x,int y,int z){
int ans=0;
ans=query(x,y)+query(y,z)+query(x,z);
ans=ans>>1;
return ans;
}
int main(){
int x,y,z;
int tot=0;
while(scanf("%d",&n)!=EOF){
if(tot++) {printf("
");}//如果最后多了一个空行就PE了
clear();
insert();
dfs(0,0);
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d%d%d",&x,&y,&z);
printf("%d
",deal(x,y,z));
}
}
return 0;
}