题面
花花有一棵带 n 个顶点的树 T，每个节点有一个点权 ai。 有一天，他认为拥有两棵树更好一些。所以，他从 T 中删去了一条边。 第二天，他认为三棵树或许又更好一些。因此，他又从他拥有的某一棵树中去除了一条边。 如此往复。每一天，花花都会删去一条尚未被删去的边，直到他得到了一个包含了 n 棵只有一个点的树的森林。 定义一条简单路径（顶点不重复的路径）的权值为路径上点权之和，一棵树的直径为树上权值最大的简单路径。花花认为树最重要的特征就是它的直径。所以他想请你算出任一时刻他拥有的所有树的直径的乘积。因为这个数可能很大，他要求你输出乘积对 109 + 7 取模之后的结果。
Input
输入的第一行包含一个整数 n，表示树 T 上顶点的数量。 下一行包含 n 个空格分隔的整数 ai，表示顶点的权值。 之后的 n - 1 行中，每一行包含两个用空格分隔的整数 xi 和 yi，表示节点 xi 和 yi 之间连有一条边，编号为 i。 再之后 n - 1 行中，每一行包含一个整数 kj，表示在第 j 天里会被删除的边的编号。
Output
输出 n 行。 在第 i 行，输出删除 i - 1 条边之后，所有树直径的乘积对 109 + 7 取模的结果。
分析
当时考试的时候想的是lca暴力乱搞一通，然后WA完了：(
然后考完了又是追悔莫及
这种正难则反，删边等效为加边的题做了多少次了..还是没长记性
思路大概就出来了，从每个节点为一棵树，没有边的末状态倒着加边，加边的时候合并树，并求直径
这里就有个简单的结论，如果a,b是树1的直径端点，c,d是树2的直径端点
则合并后的树的直径端点一定是a,b,c,d其中两个，这个结论是很显然的，根据两次dfs求直径的思想，对于树1中任意一点出发，能搜到距离最远的点作为直径的一个端点，再从此端点出发，搜到一个与它距离最远的点，就得到了直径。
所以反过来，对于树1上任意一点，到它距离最远的点要么是a，要么是b,树2同理。
接下来每次把合并后的直径乘进去，合并前的两个直径除掉（逆元）
debug好久。。先挂lca，后挂逆元，干脆我自挂东南枝算了。。。
不知道为啥费马小定理求的逆元不太对..理论上没毛病啊？？被迫改成exgcd
代码
#include<bits/stdc++.h> using namespace std; #define N 100100 #define ll long long #define mod 1000000007 long long ans,len; long long print[N]; int n,m,t,cnt; int val[N],dep[N],fas[N],first[N]; int d[N],q[N],ue[N],ve[N]; int fa[N][20]; struct email { int u,v; int nxt; }e[N*4]; struct _dot_ { int d1,d2; }tmp,dot[N*2]; inline int find(int x) { return fas[x]==x?x:fas[x]=find(fas[x]); } inline void read(int &x) { x=0;char ch=getchar(); while(ch>'9'||ch<'0'){ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} } inline void add(int u,int v) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v; } void dfs(int u,int f) { fa[u][0]=f; d[u]=d[f]+val[u]; dep[u]=dep[f]+1; for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v; if(v==f)continue; dfs(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); t=dep[x]-dep[y]; for(int i=0;(1<<i)<=t;i++) if(t&(1<<i)) x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } inline int dis(int u,int v,int l) { return d[u]+d[v]-2*d[l]+val[l]; } int x,y; void exgcd(int a,int b) { if(!b) { x=1,y=0; return; } exgcd(b,a%b); int t=x; x=y; y=t-a/b*y; } int inv(int k) { exgcd(k,mod); return (x%mod+mod)%mod; } int main() { memset(d,0,sizeof(d)); read(n);print[n]=1; for(int i=1;i<=n;i++) { read(val[i]); print[n]=(print[n]*val[i])%mod; fas[i]=dot[i].d1=dot[i].d2=i; } for(int i=1;i<n;i++) { read(ue[i]);read(ve[i]); add(ue[i],ve[i]);add(ve[i],ue[i]); } for(int i=1;i<n;i++) read(q[i]); dfs(1,0); for(int i=n-1;i>=1;i--) { int u=ue[q[i]],v=ve[q[i]]; int fax=find(u),fay=find(v); fas[fax]=fay; len=-1; ll s1=dis(dot[fax].d1,dot[fay].d2,lca(dot[fax].d1,dot[fay].d2));//12 ll s2=dis(dot[fax].d1,dot[fay].d1,lca(dot[fax].d1,dot[fay].d1));//11 ll s3=dis(dot[fax].d2,dot[fay].d2,lca(dot[fax].d2,dot[fay].d2));//22 ll s4=dis(dot[fax].d2,dot[fay].d1,lca(dot[fax].d2,dot[fay].d1));//21 ll s5=dis(dot[fax].d1,dot[fax].d2,lca(dot[fax].d1,dot[fax].d2)); ll s6=dis(dot[fay].d1,dot[fay].d2,lca(dot[fay].d1,dot[fay].d2)); len=max(s1,s2);len=max(len,s3); len=max(len,s4);len=max(len,s5);len=max(len,s6); if(len==s1) tmp.d1=dot[fax].d1,tmp.d2=dot[fay].d2; if(len==s2) tmp.d1=dot[fax].d1,tmp.d2=dot[fay].d1; if(len==s3) tmp.d1=dot[fax].d2,tmp.d2=dot[fay].d2; if(len==s4) tmp.d1=dot[fax].d2,tmp.d2=dot[fay].d1; if(len==s5) tmp=dot[fax];if(len==s6) tmp=dot[fay]; dot[fay]=tmp; print[i]=print[i+1]*len%mod; print[i]=(print[i]*inv(s5))%mod; print[i]=(print[i]*inv(s6))%mod; } for(int i=1;i<=n;i++) printf("%d ",print[i]); return 0; }