【题解】
要求出树上两点间的距离,树上的边有边权,本来应该是个LCA。
看他数据小,Xjb水过去了。。。其实也算是LCA吧,一个O(n)的LCA。。。
#include#include #define N (1010)#define rg register#define LL long longusing namespace std;int n,m,root,cnt,tot,dep[N],in[N],out[N],fa[N],last[N],a[N][N];LL ans=0;struct edge{ int to,pre,dis; }e[N<<1];inline int read(){ int k=0,f=1; char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); return k*f;}inline void add(int x,int y,int z){e[++tot]=(edge){y,last[x],z}; last[x]=tot;}void dfs(int x,int father){ in[x]=++cnt; dep[x]=dep[father]+1; for(rg int i=last[x],to;i;i=e[i].pre) if((to=e[i].to)!=father) dfs(to,fa[to]=x); out[x]=++cnt;}inline bool IN(int x,int y){ if(in[y]<=in[x]&&out[x]<=out[y]) return 1; return 0;}int main(){ n=read(); m=read(); for(rg int i=1,u,v,dis;i