萌新求调
查看原帖
萌新求调
1126361
zzx0714楼主2023/10/15 21:07

求助,我用的是点差分的板子然后把 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;
}
2023/10/15 21:07
加载中...