2026-07-01 20:16:23
发布于：上海
9阅读
0回复
0点赞
提交这一份代码
#include <bits/stdc++.h>
using namespace std;
int n,k;
int dep[105000];
int par[30][105000];
int aans[105000];
int diff[105000];
int xx[105000],yy[105000];
vector <int> v[105000];
int ans=-1;
void dfs(int x, int pa, int de){
dep[x]=de+1;
par[0][x]=pa;
for (int i=1; i<=16; i++){
par[i][x]=par[i-1][par[i-1][x]];
}
for (int i=0; i<v[x].size(); i++){
if (v[x][i]==pa) continue;
dfs(v[x][i],x,de+1);
}
}
int lca(int x, int y){
if (dep[x]<dep[y]){
swap(x,y);
}
int diff=dep[x]-dep[y];
for (int i=0; i<=16; i++){
if ((diff >> i) & 1){
x=par[i][x];
}
}
if (x==y) return x;
for (int i=16; i>=0; i--){
if (par[i][x]!=par[i][y]){
x=par[i][x];
y=par[i][y];
}
}
return par[0][x];
}
void dfs2(int x, int pa){
//aans[x]=diff[x];
for (int i=0; i<v[x].size(); i++){
if (v[x][i]==pa) continue;
dfs2(v[x][i],x);
aans[x]+=aans[v[x][i]];
}
}
int main(){
cin >> n;
for (int i=1; i<n; i++){
int x,y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
xx[i]=x;
yy[i]=y;
}
dfs(1,0,0);
cin >> k;
for (int i=1; i<=k; i++){
int x,y;
cin >> x >> y;
diff[x]++;
diff[y]++;
diff[lca(x,y)]-=2;
}
dfs2(1,0);
for (int i=1; i<n; i++){
int x=xx[i], y=yy[i];
if (dep[x]>dep[y]) cout << diff[x];
else cout << diff[y];
cout << " ";
}
}
会导致你的屏幕上出现红绿相间的条纹
这里空空如也
有帮助，赞一个