求助,我用的是点差分的板子然后把 dif[lca]--,dif[parent[lca][0]]-- 改成了 dif[lca]-=2,但是过不了样例。
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
inline int read()
{
int n=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') n=(n<<3)+(n<<1)+(c^48),c=getchar();
return n*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return;
}
vector<int>g[N];
int par[N][20],depth[N],dif[N],ans[N],q[N][2],n,k;
inline void dfs(int u,int fa)
{
for(auto v:g[u])
{
if(v==fa) continue;
par[v][0]=u;
depth[v]=depth[u]+1;
dfs(v,u);
}
return;
}
inline void sum(int u,int fa)
{
ans[u]=dif[u];
for(auto v:g[u])
{
if(v==fa) continue;
sum(v,u);
ans[u]+=ans[v];
}
}
inline int LCA(int u,int v)
{
if(u==v) return u;
if(depth[u]<depth[v]) swap(u,v);
int i,maxn=-1;
while((1<<(maxn+1))<=depth[u]) maxn++;
for(i=maxn;i>=0;i--) if((1<<i)<=depth[u]-depth[v]) u=par[u][i];
if(u==v) return u;
for(i=maxn;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
return par[u][0];
}
signed main()
{
int i,j;
n=read(),k=read();
for(i=1;i<n;i++)
{
int u,v;
u=read(),v=read();
q[i][0]=u,q[i][1]=v;
g[u].push_back(v),g[v].push_back(u);
}
dfs(1,0);
for(i=1;(1<<i)<=n;i++) for(j=1;j<=n;j++) par[j][i]=par[par[j][i-1]][i-1];
while(k--)
{
int u=read(),v=read();
int lca=LCA(u,v);
dif[u]++,dif[v]++,dif[lca]-=2;
}
sum(1,0);
for(i=1;i<n;i++)
{
if(depth[q[i][0]]<=depth[q[i][1]]) write(dif[q[i][1]]),putchar(' ');
else write(dif[q[i][0]]),putchar(' ');
}
return 0;
}