题意：先给一棵树，然后有一条额外的边，问u走到v从现在最短的路走和原来不加边走的路节省了多少距离

分析：首先跑不加边的树的LCA，这样能求出任意两点的距离，那么现在x和y多连了一条边，如果能节省路程那一定是走了xy这条边，那么暴力枚举组合，比如求u到v，新边xy，ans = min (ans, min (dux + dxy + dyv, duy + dyx + dxv))

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int N = 1e5 + 10;const int D = 20;const int INF = 0x3f3f3f3f;struct Edge	{	int v, w, nex;	Edge (int v = 0, int w = 0, int nex = 0) : v (v), w (w), nex (nex) {}}edge[N<<1];int head[N], dep[N], rt[D][N];int d[N];int n, q, e;int x, y, cost;void init(void)	{	memset (head, -1, sizeof (head));	e = 0;}void add_edge(int u, int v, int w)	{	edge[e] = Edge (v, w, head[u]);	head[u] = e++;}void DFS(int u, int fa, int deep, int len)	{	dep[u] = deep;	d[u] = len;	rt[0][u] = fa;	for (int i=head[u]; ~i; i=edge[i].nex)	{		int v = edge[i].v, w = edge[i].w;		if (v == fa)	continue;		DFS (v, u, deep + 1, len + w);	}}int LCA(int u, int v)	{	if (dep[u] < dep[v])	swap (u, v);	for (int i=0; i
          
           > i & 1) { u = rt[i][u]; } } if (u == v) return u; for (int i=D-1; i>=0; --i) { if (rt[i][u] != rt[i][v]) { u = rt[i][u]; v = rt[i][v]; } } return rt[0][u];}int solve(int u, int v) { int lca = LCA (u, v); int ans = d[u] + d[v] - d[lca] * 2; int lca1 = LCA (u, x); int dux = d[u] + d[x] - d[lca1] * 2; int lca2 = LCA (u, y); int duy = d[u] + d[y] - d[lca2] * 2; int lca3 = LCA (v, x); int dvx = d[v] + d[x] - d[lca3] * 2; int lca4 = LCA (v, y); int dvy = d[v] + d[y] - d[lca4] * 2; int mn = min (dux + dvy + cost, duy + dvx + cost); if (mn > ans) return 0; else return ans - mn;}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { init (); scanf ("%d%d", &n, &q); for (int u, v, w, i=1; i