每日一题 day27 打卡
Analysis
对于每条非树边 , 覆盖 x 到 LCA 和 y到 LCA 的边 , 即差分算出每个点和父亲的连边被覆盖了多少次 .
被覆盖 0 次的边可以和 m 条非树边搭配 , 被覆盖 1 次的边可以和唯一的非树边搭配 , 2 次以上的不能产生贡献 .
时间复杂度 O(n+m)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define maxn 100000+10
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
int n,m,cnt;
int head[*maxn],dep[maxn],sum[*maxn],c[*maxn];
int dp[maxn][];
struct node
{
int v,nex;
}edge[*maxn];
inline void print(int x)
{
write(x);
printf("\n");
}
inline void add(int x,int y)
{
edge[++cnt].v=y;
edge[cnt].nex=head[x];
head[x]=cnt;
}
inline void init(int from,int fa)
{
dep[from]=dep[fa]+;
for(int i=;i<=;i++)
dp[from][i]=dp[dp[from][i-]][i-];
for(int i=head[from];i;i=edge[i].nex)
{
int to=edge[i].v;
if(to==fa) continue;
dp[to][]=from;
init(to,from);
}
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=;i>=;i--)
{
if(dep[dp[x][i]]>=dep[y]) x=dp[x][i];
if(x==y) return x;
}
for(int i=;i>=;i--)
if(dp[x][i]!=dp[y][i])
{
x=dp[x][i];
y=dp[y][i];
}
return dp[x][];
}
inline void dfs(int from,int fa)
{
for(int i=head[from];i;i=edge[i].nex)
{
int to=edge[i].v;
if(to==fa) continue;
dfs(to,from);
sum[from]+=sum[to];
}
}
signed main()
{
n=read();m=read();
for(int i=;i<=n-;i++)
{
int x=read(),y=read();
add(x,y);add(y,x);
}
init(,);
for(int i=;i<=m;i++)
{
int x=read(),y=read();
sum[x]++,sum[y]++,sum[lca(x,y)]-=;
}
dfs(,);
int ans=;
for(int i=;i<=n;i++)
{
if(sum[i]==) ans+=m;
if(sum[i]==) ans++;
}
print(ans);
return ;
}
请各位大佬斧正