CF379F New Year Tree

思路:一开始上手的时候感觉非常棘手,需要动态维护一个树的直径,没有什么思路. 查看一些题解后,发现还是需要一些做题的灵感的,在这个题里面可以大胆假设下. 每次答案变化的时候,一定是直径的两个端点发生了变化,那么可以用lca分别计算树上的距离来查看新添加的点是否会成为新直径的端点即可,然后动态维护这两个端点,但可能的漏洞就是有没有可能选取不同的端点使得直径的计算出现错误,不管这个漏洞,我们尝试提交程序,结果居然发现ac了

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int fa[maxn][31];int depth[maxn];
void dfs1(int u,int f){
	fa[u][0]=f;depth[u] = depth[f] +1;
	for(int i=1;iq;
	int cur = 2;int n=4;
	while(q--){
		int x;cin>>x;
		int a = n+1,b=n+2;
		G[x].pb(n+1);G[n+1].pb(x);
		G[x].pb(n+2);G[n+2].pb(x);
		n+=2;
		dfs1(a,x);dfs1(b,x);
		int f1 = lca(a,u);int f2 = lca(a,v);
		int len1 = depth[a] + depth[u] -2*depth[f1];
		int len2 = depth[a] + depth[v] -2*depth[f2];
		if(len1==cur+1) {
			v = a;cur++;
		}
		else if(len2==cur+1){
			u = a;cur++;
		}
		cout