今天照常7:45开始打模拟赛，11:45时结束。打了T1的40分暴力、T3的20分暴力，没有注意到T4的特殊样例可以骗分（悲），最后以60分收尾。总结一下，没有挂分，但也没和正解挨上边，算是不好也不坏吧。
订题时我看着T1 26行的AC代码陷入了沉思。三个人，想了至少三个小时，结果全没想出来，于是来整理一下今天的神奇模拟赛。
题目小链接：？
T1【集合】
题目大意：给定一棵n个节点的树，共m次操作，每次操作形如对于第x条边(u,v)，将Su,Sv替换成两者的并集。求m次操作后，每个i属于多少个集合
解题思路：经过一定的思考之后，我们发现正序操作可以理解为“我会有多少个朋友”，明显不好处理；但倒序操作可以理解为“我会是谁的朋友”，可以转移。
举个栗子：对于操作加盟u->v边，此时u与v中都包含彼此，所以当下次对u进行操作时，v一定也会被那个节点包含。
可以转移为s[u]=s[v]=s[u]+s[v]。但这样当出现重边时，因为u与v已有相同元素，这个操作就会应取了相同元素而不满足集合性质（题目中取并集）。但是，众所周知,|S∪T|=|S|+|T|−|S∩T|，而经过一系列推论我们容易发现|S∩T|为上一次对该边操作后的答案，即上一次操作取的并集会是此次操作中u与v的交集。那么会不会出现|S∩T|中不仅仅是上次并集中的元素情况呢？手模后发现是不会的。因为……反正……这样这样，那样那样，树上是没有环的，若S、T中的其他元素想要影响|S∩T|，只能通过再次操作该边影响，所以上次的操作的集合并就是这次操作中的集合角。
于是乎，我们维护pre数组与ans数组，pre[i]表示对于边i，上一次操作的答案，ans[i]表示对于节点i之中元素的个数。于是我们稍加整理，可以得到神奇的式子：ans[u]=ans[v]=pre[op[i]]=ans[u]+ans[v]-pre[op[i]]。于是26行代码就解决了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int n,m;
int u[N],v[N];//记录每条边
int op[N];//操作
int ans[N],pre[N];//答案与上次答案
void read()
{
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++) scanf("%d%d",&u[i],&v[i]);
for (int i=1;i<=m;i++) scanf("%d",&op[i]);
}
int main()
{
read();
for (int i=1;i<=n;i++) ans[i]=1;
for (int i=m;i>=1;i--)
{
int uu=u[op[i]],vv=v[op[i]];
ans[uu]=ans[vv]=pre[op[i]]=ans[uu]+ans[vv]-pre[op[i]];
}
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}