题目链接

思路：就是裸的树上差分，但有的数据我的代码啥也没输出

代码：

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define MAX_N 10010
#define MAX_M 10010
int n,m;
struct graph1{
    vector<int> next;
    int qz = 0;
}node[MAX_N];
struct graph2{
    int u,v;
}edge_m[MAX_M];
int d[MAX_N],f[MAX_N][20];
void bfs(int v){
    queue<int> q;
    int t = (int)(log(n) / log(2)) + 1;
    q.push(v);
    d[v] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0;i < node[x].next.size();i++){
            int y = node[x].next[i];
            if(d[y] != 0) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++)
                f[y][j] = f[f[y][j - 1]][j - 1];
            q.push(y);
        }
    }
}
int LCA(int x,int y){
    int t = (int)(log(n) / log(2)) + 1;
    if(d[x] > d[y]) 
       swap(x,y);
    for(int i = t;i >= 0;i--)
        if(d[f[y][i]] >= d[x])
           y = f[y][i];
    if(x == y) return x;
    for(int i = t;i >= 0;i--)
        if(f[x][i] != f[y][i])
           x = f[x][i],y = f[y][i];
    return f[x][0];
}
int F[MAX_N];
int dfs(int x,int father){
    int qz_t = node[x].qz;
    for(int i = 0;i < node[x].next.size();i++){
        int v = node[x].next[i];
        if(v != father)
            qz_t += dfs(v,x);
    }
    return F[x] = qz_t;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n - 1;i++){
        int u,v;
        cin >> u >> v;
        node[u].next.push_back(v);
        node[v].next.push_back(u);
    }
    bfs(1);
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        node[u].qz++;
        node[v].qz++;
        node[LCA(u,v)].qz -= 2;
    }
    dfs(1,-1);
    int t = 0;
    for(int i = 2;i <= n;i++) {
        if(F[i] == 1)
           t++;
        else if(F[i] == 0)
           t += m;
    }
    cout << t;
    return 0;
}