【JZOJ A组】宝藏
Description
Input
Output
Sample Input
2
3
1 0
1 2
2
1 0 1
2 0 2 1
4
0 1
2 0
3 0
1
3 0 1 0 1
Sample Output
1.0000
5.0000
<空行>
11.0000
Data Constraint
思路
与一题很像,只是询问改了:https://blog.csdn.net/Eric1561759334/article/details/81674235
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=1e6+77;
struct E
{
int to,next;
}e[maxn<<1];
int list[maxn],n,q,cnt,v[577];
ll fa[maxn][22],dep[maxn];
double f[maxn],g[maxn],ans;
void add(int u,int v)
{
e[++cnt].to=v; e[cnt].next=list[u]; list[u]=cnt;
}
void dfs(int u,int father)
{
fa[u][0]=father; f[u]=0;
for(int i=list[u]; i; i=e[i].next)
{
int v=e[i].to;
if(v==father) continue;
dfs(v,u);
f[u]+=f[v]+1.0;
}
f[u]++;
}
void dfs1(int u,int father)
{
double s=0;
for(int i=list[u]; i; i=e[i].next)
if(e[i].to!=father) s+=f[e[i].to]+1.0;
else s+=g[u]+1.0;
for(int i=list[u]; i; i=e[i].next)
{
int v=e[i].to;
if(v==father) continue;
g[v]=s-f[v];
dfs1(v,u);
}
}
void dfs2(int u,int father)
{
dep[u]=dep[father]+1;
f[u]=f[u]+f[father]; g[u]=g[u]+g[father];
for(int i=list[u]; i; i=e[i].next)
{
int v=e[i].to; if(v==father) continue;
dfs2(v,u);
}
}
int getlca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
if(d) for(int i=0; i<=log2(n)+1&&d; i++,d>>=1) if(d&1) u=fa[u][i];
if (u==v) return u;
for(int i=log2(n)+1; i>=0; i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
double solve(int u,int v)
{
int lca=getlca(u,v);
return f[u]-f[lca]+g[v]-g[lca];
}
int main()
{
freopen("data.in","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
memset(fa,0,sizeof(fa)); memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
memset(e,0,sizeof(e)); memset(list,0,sizeof(list)); memset(dep,0,sizeof(dep));
scanf("%d",&n);
for(int i=1; i<=n-1; i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x+1,y+1); add(y+1,x+1);
}
dfs(1,0);
f[1]=0; g[1]=0;
dfs1(1,0); dfs2(1,0);
for(int i=1; i<=log2(n)+1; i++)
{
for (int j=1; j<=n; j++) fa[j][i]=fa[fa[j][i-1]][i-1];
}
scanf("%d",&q);
while(q--)
{
ans=0;
int p;
scanf("%d%d",&p,&v[0]);
v[0]++;
for(int i=1; i<=p; i++) scanf("%d",&v[i]),v[i]++;
for(int i=1; i<=p; i++) ans+=solve(v[i-1],v[i]);
printf("%.4lf\n",ans);
}
printf("\n");
}
}