Description：

给出一棵树，维护点集 $S$ ，如果 $S$ 的大小是偶数，输出：如果将 $S$ 中的点两两连上边权为树上距离的边，那么 $S$ 里的最小权完美匹配是多少。

$n,q\leqslant 10^6$

Solution：

首先注意到一个事实是，匹配边一定不相交，不然一定可以通过转化使得总长度更小，然后考虑静态时候的情况，会发现某条边选不选只会由子树内特殊点的奇偶性决定，因此再考虑插入一个点对的变化，会发现是他们这条路径上的点子树内特殊点的奇偶性改变，也就是说这条路径上的匹配边和非匹配边交换，因此用 $LCT$ 维护匹配边的和就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

struct node

{

    int fa,c[2];

    bool rev;

    int w,siz,val,sum,tag;

    node(){fa = c[0] = c[1] = 0;siz = sum = tag = 0;rev = false;}

}t[MAXN];

void pushdown(int rt)

{

    if(t[rt].rev)

    {

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	if(t[rt].tag)

	{

		t[t[rt].c[0]].sum = t[t[rt].c[0]].siz - t[t[rt].c[0]].sum;

		t[t[rt].c[1]].sum = t[t[rt].c[1]].siz - t[t[rt].c[1]].sum;

		t[t[rt].c[0]].tag ^= 1;t[t[rt].c[1]].tag ^= 1;

		if(t[rt].c[0] > n)t[t[rt].c[0]].val ^= 1;

		if(t[rt].c[1] > n)t[t[rt].c[1]].val ^= 1;

		t[rt].tag = 0;

	}

    return;

}

void maintain(int rt)

{

	t[rt].sum = t[t[rt].c[0]].sum + t[t[rt].c[1]].sum + t[rt].val;

	t[rt].siz = t[t[rt].c[0]].siz + t[t[rt].c[1]].siz + t[rt].w;

	return;

}

int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

bool isroot(int x){return (t[t[x].fa].c[0] != x && t[t[x].fa].c[1] != x);}

void rotate(int x)

{

    register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

    if(!isroot(y))t[z].c[fy] = x;

    t[x].fa = z;

    connect(t[x].c[fx^1],y,fx);

    connect(y,x,fx^1);

    maintain(y);maintain(x);

    return; 

}

int stack[MAXN],top = 0;

void splay(int x)

{

	stack[++top] = x;

	for(int i = x;!isroot(i);i = t[i].fa)stack[++top] = t[i].fa;

	while(top)pushdown(stack[top--]);

    while(!isroot(x))

    {

        register int y = t[x].fa;

        if(isroot(y)){rotate(x);break;}

        if(id(x) == id(y)){rotate(y);rotate(x);}

        else{rotate(x);rotate(x);}

    }

    return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int a,int b){makeroot(a);t[a].fa = b;return;}

int val[MAXN],tot = 0;

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		link(a,i + n);link(b,i + n);

		t[i + n].siz = t[i + n].w = 1;

	}

	scanf("%d",&m);

	int ans = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		if(val[a] == val[b])

		{

			if(val[a] == 0)++tot;

			else --tot;

		}

		val[a] ^= 1;val[b] ^= 1;

		makeroot(a);access(b);splay(b);

		ans = ans - t[b].sum;

		t[b].sum = t[b].siz - t[b].sum;

		t[b].tag ^= 1;

		ans = ans + t[b].sum;

		cout << ans << endl;

	}

    return 0;

}