Imakf是一个小蒟蒻，他最近刚学了LCA，他在手机APP里看到一个游戏也叫做LCA就下载了下来。

9 +7)

M行，每行一个数，第ii行的数表示有多少组点对(u_i,v_i)的最近公共祖先是P_i

``````#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define fo(i) for(int i=1;i<n;i++)
#define Fo(j) for(int j=1;j<=m;j++)
using namespace std;
const int N=500005;
const int M=2000003;
const int modd=1e9+7;
int n,m,s,tot;
int dep[N],ans[N];
struct NODE{

int to,nex;
}bian[M];
struct Node{

int son,dep,fa;
}dian[N];

int 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;
}

++tot;
bian[tot].to=y;
}
void dfs(int xx,int fa){

dian[xx].son=1;

if(bian[i].to!=fa){
//这个儿子不是爹
dian[bian[i].to].fa=xx;
dian[bian[i].to].dep=dian[xx].dep+1;
dfs(bian[i].to,xx);
dian[xx].son+=(dian[bian[i].to].son%modd);
}
}
}
inline int solve(int xx){

int ans=dian[xx].son;

if(dian[bian[i].to].dep>dian[xx].dep){

ans=ans+(dian[xx].son-dian[bian[i].to].son)*dian[bian[i].to].son;
}
}
return ans;

}
int main(){

fo(i){

int a,b;
}
dian[0].dep=0;
dfs(s,0);
for(int i=1;i<=n;i++) ans[i]=solve(i);
Fo(j){

int p;
printf("%d\n",ans[p]);
}
return 0;
}

``````

2022-12-07 18:37

2022-12-23 00:18

2022-12-03 23:52

2022-12-16 22:45

2022-12-15 00:41

2022-12-29 13:09
Durham University_2022

2022-12-22 18:27

2022-12-09 14:30

2022-12-23 19:49

2022-12-14 16:03

2022-12-19 19:04