Solution
E
从每个 \(i\) 向 \(a_i\) 连边，建出来一颗内向基环树。那么答案相当于非环节点到环上距离 + 若干倍整个环的和 + 环上一段路径和。预处理环上前缀和与节点到环的距离即可。代码不放了。
F
树上节点统一用 \(1~n\) 编号。
对答案拆一下贡献，即可发现要求对每个 \(i\)，包含节点 \(1~i\) 的路径条数和。那么首先如果 \(1~i\) 都不在一条路径上肯定直接 break。
对结点 \(1\) 特判。不妨定义 \(L\)，\(R\) 表示同时包含节点 \(1~i\) 的最短链的两端，\(dis(i,j)\) 表示树上两点间距离，\([i,j]\) 表示树上两点间路径。
先考虑加入节点 \(i\) 时 \(L\) 和 \(R\) 的变化。如果 \(dis(i,L)+dis(i,R)=dis(L,R)\)，说明 \(i\) 已经在路径上，无变化；\(dis(i,L)+dis(L,R)=dis(i,R)\) 说明 \(L\) 在路径 \([i,R]\) 上，把 \(i\) 赋值给 \(L\)。\(R\) 在路径 \([i,L]\) 上同理。三种情况都不满足，直接 break 即可。
然后考虑已知 \(L\)，\(R\) 如何计算答案。不妨钦定 \(L\) 的深度不大于 \(R\) 的深度。分 \(2\) 种情况讨论：
- \(L\) 为 \(R\) 的祖先。定义 \(son\) 为 \(L\) 的某个儿子，且 \(son\) 为 \(R\) 的祖先。则答案增加 \((n-sz_son)\times sz[R]\)。
- \(L\) 和 \(R\) 不为祖先-后代关系。则答案增加 \(sz_L \times sz_R\)。
需要倍增求 LCA，复杂度 \(O(n \log n)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,lg[N];
vector<int>G[N];
int dep[N],sz[N],fa[20][N];
void dfs(int x,int f)
{dep[x]=dep[f]+1;fa[0][x]=f;sz[x]=1;ll sum=0;for(auto y:G[x]){if(y==f)continue;dfs(y,x);sz[x]+=sz[y];sum+=sz[y];}
}
int lca(int u,int v)
{if(dep[u]<dep[v])swap(u,v);for(int i=lg[n];i>=0;i--)if(dep[fa[i][u]]>=dep[v])u=fa[i][u];if(u==v)return u;for(int i=lg[n];i>=0;i--)if(fa[i][u]!=fa[i][v])u=fa[i][u],v=fa[i][v];return fa[0][u];
}
int dis(int x,int y)
{int g=lca(x,y);return dep[x]+dep[y]-2*dep[g];
}
int getk(int u,int v)
{for(int i=lg[n];i>=0;i--)if(dep[fa[i][u]]>dep[v])u=fa[i][u];return u;
}
signed main()
{cin>>n;for(int i=2;i<=n;i++){lg[i]=lg[i>>1]+1;int u,v;cin>>u>>v;u++,v++;G[u].emplace_back(v);G[v].emplace_back(u);}dfs(1,0);for(int i=1;i<=lg[n];i++)for(int j=1;j<=n;j++)fa[i][j]=fa[i-1][fa[i-1][j]];int tp=1,ed=1;ll ans=n*(n+1)/2;for(auto i:G[1])ans-=sz[i]*(sz[i]+1)/2;for(int i=2;i<=n;i++){int x=dis(i,tp),y=dis(i,ed),z=dis(tp,ed);if(x+z==y) tp=i;else if(z+y==x)ed=i;else if(x+y!=z)break;if(dep[tp]>dep[ed])swap(tp,ed);int g=lca(tp,ed);if(g==tp)ans+=1ll*(n-sz[getk(ed,tp)])*sz[ed];else ans+=1ll*sz[tp]*sz[ed];}cout<<ans<<"\n";return 0;
}