学步园

#include <stdio.h>
#include <cstring>
struct edge
{
    int to,next,w;
};
int n,m,t,h;
edge q[40001<<1],rq[401];//q存的是原数组，rq存的是询问数组。
int head[40001],head1[40001],dis[40001],f[40001];//dis表示当前节点到跟节点的距离。
bool vis[40001];
void add1(int i,int j,int w)
{
    q[t].to=j;
    q[t].w=w;
    q[t].next=head[i];
    head[i]=t++;
}
void add2(int i,int j)
{
    rq[h].w=-1;
    rq[h].to=j;
    rq[h].next=head1[i];
    head1[i]=h++;
}
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
void lca(int u,int dist)
{
    f[u]=u;
    vis[u]=true;
    dis[u]=dist;
    for(int i=head1[u]; i!=-1; i=rq[i].next)//对询问的数组应当先处理，否则会wa。
    {
        int v=rq[i].to;
        if(vis[v])
            rq[i].w=dis[u]+dis[v]-2*dis[find(f[v])];//这一步倘若直接将它的相邻边赋上相同值会爆栈，不解？
    }
    for(int i=head[u]; i!=-1; i=q[i].next)
    {
        int v=q[i].to;
        if(!vis[v])
        {
            lca(v,dist+q[i].w);
            f[v]=u;
        }
    }
}
int main()
{
    int tt,u,v,w;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        memset(head1,-1,sizeof(head1));
        memset(head,-1,sizeof(head));
        memset(vis,false,sizeof(vis));
        memset(q,0,sizeof(q));
        memset(rq,0,sizeof(rq));
        t=h=0;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add1(u,v,w);
            add1(v,u,w);
        }
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add2(u,v);
            add2(v,u);
        }
        lca(1,0);
        for(int i=0; i<h; i+=2)
        {
            if(rq[i].w!=-1) printf("%d\n",rq[i].w);
            else printf("%d\n",rq[i^1].w);
        }
    }
    return 0;
}