Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
68322 seanlsy 树上路径 C++ 解答错误 5 89 MS 14708 KB 1496 2023-01-29 14:11:44

Tests(1/20):


#include <bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48); return f*x; } int n,q,x,y,z,tim,f[100005][22],lg[100005],dep[100005]; vector<int> son[100005]; void dfs(int x){ dep[x]=dep[f[x][0]]+1; for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=0;i<son[x].size();i++) dfs(son[x][i]); } inline int lca(int u,int v){ if(dep[u]<dep[v]) swap(u,v); while(dep[u]>dep[v]) u=f[u][lg[dep[u]-dep[v]]]; for(int i=lg[dep[u]];(u^v)&&(~i);i--) if(f[u][i]^f[v][i]) u=f[u][i],v=f[v][i]; return (u^v)?f[u][0]:u; } inline int solve(int a,int b,int c){ int lca1=lca(a,b),lca2=lca(a,c); if(lca1^lca2) return min(dep[a]-dep[lca1],dep[a]-dep[lca2])+1; return dep[a]-dep[lca1]+1+min(dep[b]-dep[lca1],dep[c]-dep[lca1]); } int main(){ //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); n=read(),q=read(); for(int i=1;i<=n;i++) lg[i]=lg[i-1]+((1<<lg[i-1]+1)==i); for(int i=2;i<=n;i++) f[i][0]=read(),son[f[i][0]].push_back(i),tim+=(f[i][0]==i-1); if(tim==n-1){ while(q--){ x=read(),y=read(),z=read(); if(x>y) swap(x,y); if(x>z) swap(x,z); if(y>z) swap(y,z); printf("%d\n",max(y-x,z-y)+1); } return 0; } dfs(1); while(q--) x=read(),y=read(),z=read(),printf("%d\n",max(solve(x,y,z),max(solve(y,x,z),solve(z,x,y)))); return 0; }


测评信息: