题面：https://www.cnblogs.com/Juve/articles/11598286.html
attack：
支配树裸题？
看一下支配树是什么：
问题：我们有一个有向图(可以有环)，定下了一个节点为起点s。现在我们要求：从起点s出发，走向一个点p的所有路径中，必须要经过的点有哪些{xp}。
换言之，删掉{xp}中的任意一个点xpi以及它的入边出边，都会使s无法到达p。
对于此题而言，建出支配树就可以了
具体步骤：
我们用bfs实现，在新树中，一个节点x要连向原图上所有能到它的点在新树上的lca
根据这个思路，我们采用拓扑，在减去一个点的入度的同时更新它在新树上的父节点
如果它的度数变为0，那么用倍增lca的方式将它加入到新图中
建出了树，那么每一个询问的答案就是所有询问节点的lca在新树上的lca
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define re register
using namespace std;
const int MAXN=5e4+5;
const int MAXM=1e5+5;
int n,m,Q,k,ans=0,du[MAXN];
int to[MAXM<<1],nxt[MAXM<<1],pre[MAXN],cnt=0;
inline void add(re int u,re int v){
++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
int f[MAXN][22],deep[MAXN];
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int k=deep[x]-deep[y];
for(int i=0;i<=20;i++)
if((1<<i)&k)
x=f[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
queue<int>q;
void bfs(int st){
deep[st]=1;
q.push(st);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(!f[y][0]) f[y][0]=x;
else f[y][0]=LCA(f[y][0],x);
f[y][0]=f[y][0];
deep[y]=deep[f[y][0]]+1;
--du[y];
if(!du[y]){
q.push(y);
for(int j=0;j<=20;++j){
if(f[y][j-1]) f[y][j]=f[f[y][j-1]][j-1];
}
}
}
}
}
signed main(){
scanf("%d%d%d",&n,&m,&Q);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);++du[v];
}
bfs(1);
while(Q--){
scanf("%d",&k);
scanf("%d",&ans);
for(int i=1,vi;i<k;++i){
scanf("%d",&vi);
ans=LCA(ans,vi);
}
printf("%d\n",deep[ans]);
}
return 0;
}tree：
简单树形dp？
概率是在逗你玩的
设size[x]表示x的子树大小，dp[x]表示第一次到x的期望次数，那么：
$dp[x]=dp[fa]+2*(n-size[x])+1$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;
void add(int u,int v){
++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
int siz[MAXN],dp[MAXN];
void dfs(int x,int fa){
siz[x]=1;
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dfs(y,x);
siz[x]+=siz[y];
}
}
void DFS(int x,int fa){
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dp[y]=dp[x]+2*(n-siz[y])-1;
DFS(y,x);
}
}
signed main(){
scanf("%lld",&n);
for(int i=1,u,v;i<n;++i){
scanf("%lld%lld",&u,&v);
add(u,v),add(v,u);
}
dfs(1,0);
dp[1]=1;
DFS(1,0);
for(int i=1;i<=n;++i){
printf("%0.3lf\n",(double)dp[i]);
}
return 0;
}