思路：
转化为差分，输出边上深度最深的点的答案。
关于我把数组开小了然后不停地找bug这件事
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn =2e5+7; struct LCA { int fa[maxn][25], dep[maxn]; int e[maxn],ne[maxn],m; int h[maxn], idx = 0,n,root; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++;///链式前向星存图 } void init() { memset(h, -1, sizeof h); idx = 0; /*for(int i=1;i<n;i++){ int u=read,v=read; add(u,v);add(v,u); }*/ } void bfs(int root) { queue<int>q; memset(dep, 0x3f, sizeof dep); dep[0] = 0; ///特殊处理 dep[root] = 1; q.push(root); while(!q.empty()) { int t = q.front(); q.pop(); for(int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if(dep[j] > dep[t] + 1) { dep[j] = dep[t] + 1; q.push(j); fa[j][0] = t; ///预处理fa数组 for(int k = 1; k <= 20; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } int lca(int a, int b) { if(dep[a] < dep[b]) swap(a, b); for(int k = 20; k >= 0; k--) if(dep[fa[a][k]] >= dep[b]) a = fa[a][k]; ///使a,b跳到同一层 if(a == b) return a; for(int k = 20; k >= 0; k--) if(fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k]; return fa[a][0]; } }; LCA l; int d[maxn]; PII pos[maxn]; void dfs(int u,int fa){ for(int i=l.h[u];~i;i=l.ne[i]){ int j=l.e[i]; if(j==fa) continue; dfs(j,u); d[u]+=d[j]; } } int main(){ l.init(); l.n=read; for(int i=1;i<l.n;i++){ int u=read,v=read; pos[i]={u,v}; l.add(u,v);l.add(v,u); } l.bfs(1); int m=read; for(int i=1;i<=m;i++){ int u=read,v=read; d[u]++;d[v]++;d[l.lca(u,v)]-=2; } dfs(1,0); for(int i=1;i<l.n;i++){ int d1=l.dep[pos[i].first],d2=l.dep[pos[i].second]; if(d1>d2) cout<<d[pos[i].first]<<" "; else cout<<d[pos[i].second]<<" "; } return 0; }
