题目描述：

秀秀有一棵带?个顶点的树?，每个节点有一个点权?-。

有一天，她想拥有两棵树，于是她从?中删去了一条边。

第二天，她认为三棵树或许会更好一些。因此，她又从她拥有的某一棵树中删去了一条边。

如此往复，每一天秀秀都会删去一条尚未被删去的边，直到她得到由?棵只有一个点的树构成的

森林。

秀秀定义一条简单路径（节点不重复出现的路径）的权值为路径上所有点的权值之和，一棵树的

直径为树上权值最大的简单路径。秀秀认为树最重要的特征就是它的直径。所以她想请你算出任一时

刻她拥有的所有树的直径的乘积。因为这个数可能很大，你只需输出这个数对10. + 7取模之后的结

果即可。

输入：

输入的第一行包含一个整数?，表示树?上顶点的数量。

下一行包含?个空格分隔的整数?-，表示顶点的权值。

之后的? − 1行中，每一行包含两个用空格分隔的整数?-和?-，表示节点?-和?-之间连

有一条边，编号为?。

再之后? − 1行中，每一行包含一个整数?6，表示在第?天里会被删除的边的编号。

输出：

共?行，在第?行，输出删除? − 1条边之后，所有树直径的乘积对10. + 7取模的结果。

数据范围：

对于40%的数据：? ≤ 100;

另有20%的数据：? ≤ 1000;

另有20%的数据：? ≤ 10000;

对于100%的数据：? ≤ 100000,?- ≤ 10000。

算法标签：LCA，倍增

思路：

两棵树合并时，树的直径只有可能由原来两棵树直径两边的点构成，所以枚举四个点构成的直径比较大小（在原树中利用lca比较log效率）。然后就一直把树合起来就行了。

以下代码：

#include
      
       #define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e5+5,p=1e9+7;LL res[N],sum=1,g[N],s[N];int n,a[N],head[N],ne[N<<1],to[N<<1],cnt,k[N],pi[2][N],f[N][20],d[N],fa[N],len[N];struct node{
    int l,r;}t[N];il int read(){
    int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}il void insert(int x,int y){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}il LL ksm(LL a,int y){LL b=1;while(y){
    if(y&1)b=b*a%p;a=a*a%p;y>>=1;}return b;}il int getfa(int x){
    if(fa[x]==0)return x;return fa[x]=getfa(fa[x]);}il void dfs(int x){    for(int i=head[x];i;i=ne[i]){        if(f[x][0]==to[i])continue;        s[to[i]]=s[x]+(LL)a[to[i]];d[to[i]]=d[x]+1;        f[to[i]][0]=x;dfs(to[i]);    }}il void init(){    for(int i=1;i<=18;i++)for(int j=1;j<=n;j++)        f[j][i]=f[f[j][i-1]][i-1];}il int LCA(int x,int y){    if(d[x]
       
        =0;i--)if(d[f[x][i]]>=d[y])x=f[x][i];    if(x==y)return x;    for(int i=18;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];    return f[x][0];}int main(){    n=read();for(int i=1;i<=n;i++)a[i]=read(),g[i]=a[i];    for(int i=1;i
        
         r)r=qq,t1=xx,t2=yy;            }        }        if(len[x]>r)r=len[x],t1=pi[0][x],t2=pi[1][x];        if(len[y]>r)r=len[y],t1=pi[0][y],t2=pi[1][y];        pi[0][x]=t2;pi[1][x]=t1;g[x]=r;fa[y]=x;len[x]=r;        sum=sum*r%p;res[i]=sum;    }    for(int i=1;i<=n;i++)printf("%lld\n",res[i]);  return 0;}