感谢@JCarlson 提供题目和题意

题意:

给你一个带权图,求路径上权值和

做法:

LCA..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int up[40005][25];
int sum[40005][25];
int father[40005];
int up_val[40005];
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[1000005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts(y,x,z);
}
int depth[40005];
void dfs(int x)
{
    up[x][0]=father[x];
    sum[x][0]=up_val[x];
    int i;
    for (i=1;i<20;i++)
    {
        if (up[x][i-1]==-1)
        {
            up[x][i]=-1;
            sum[x][i]=sum[x][i-1];
        }
        else
        {
            up[x][i]=up[up[x][i-1]][i-1];
            sum[x][i]=sum[x][i-1]+sum[up[x][i-1]][i-1];
        }
    }
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        father[t->y]=x;
        up_val[t->y]=t->weight;
        depth[t->y]=depth[x]+1;
        dfs(t->y);
    }
}
int lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    int t=depth[x]-depth[y];
    int i;
    int ans=0;
    for (i=0;i<20;i++)
    {
        if ((1<<i)&t)
        {
            ans+=sum[x][i];
            x=up[x][i];
        }
    }
    if (x==y) return ans;
    for (i=19;i>=0;i--)
    {
        if (up[x][i]!=up[y][i])
        {
            ans+=sum[x][i];
            ans+=sum[y][i];
            x=up[x][i];
            y=up[y][i];
        }
    }
    return ans+sum[x][0]+sum[y][0];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        memset(li,0,sizeof(li));
        int n,m;
        scanf("%d%d",&n,&m);
        int i;
        for (i=1;i<n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            x--;
            y--;
            insert_edge(x,y,z);
        }
        father[0]=-1;
        up_val[0]=0;
        depth[0]=0;
        dfs(0);
        for (i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            printf("%d\n",lca(x,y));
        }
    }
    return 0;
}