Description：

从点 $1$ 出发，一条路径的权值是边上的权值的异或和，问能得到多少种权值，支持删边。

$1\leqslant n\leqslant 10^5,1\leqslant w\leqslant 10^{18}$

Solution：

先考虑没有删边怎么做，可以先按照套路找出一个生成树，然后把所有环的权值丢到一棵生成树中，然后求出每个点到 $1$ 的随便一条路径的权值，然后问题就变成了给你一个集合和一个线性基，选集合中的一个数和线性基中的数随便异或问总共能得到多少个数，那么我们可以求出这个集合中不能通过线性基互相得到的类的个数 $siz$ ，同一类中的数可以用这个线性基异或得到，那么答案就是 $siz\times 2^{\text{线性基元素个数}}$ ，划分等价类的方法是把每个数都削成在该线性基中能表示成的最小的数，这个一样的就是一个等价类。然后再考虑删边，肯定是时光倒流变成加边，我们在合并两个联通块的时候可以暴力求出不包括一的联通块的等价类划分，这个均摊是 $O(n)$ 的因为每个点只会计算一次，但是我们插入时线性基可能会变，但是发现线性基的有效插入实际上只有 $\log w$ 次，于是每次暴力重构等价类划分即可，时间复杂度 $O(n\log^2w+(m+q)\alpha(n))$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

typedef long long ll;

#define MAXN 200010

struct LinearBase

{

	ll d[63];

	ll ans;

	LinearBase(){memset(d,0,sizeof(d));ans = 1;}

	bool add(ll x)

	{

		for(int i = 62;i >= 0;--i)

		{

			if(x & (1ll << i))

			{

				if(d[i] == 0)

				{

					d[i] = x;

					ans = ans * 2;

					return true;

				}

				else

				{

					x ^= d[i];

				}

			}

		}

		return false;

	}

	ll query_min(ll x)

	{

		for(int i = 62;i >= 0;--i)

		{

			if((x ^ d[i]) < x)x ^= d[i];

		}

		return x;

	}

}s;

struct edges

{

	int u,v;

	ll w;

}es[MAXN];

int cut[MAXN];

ll ans[MAXN];

bool tag[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

set<ll> t;

struct edge

{

	int to,nxt;

	ll w;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

ll val[MAXN],id[MAXN];

bool vis[MAXN];

void rebuild()

{

	t.clear();

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

	{

		if(!vis[i])continue;

		id[i] = s.query_min(val[i]);

		t.insert(id[i]);

	}

	return;

}

void dfs(int k,ll depth)

{

	val[k] = depth;

	id[k] = s.query_min(val[k]);

	t.insert(id[k]);

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])

		{

			if(s.add(val[e[i].to] ^ val[k] ^ e[i].w))rebuild();

		}

		else

		{

			dfs(e[i].to,depth ^ e[i].w);

		}

	}

	return;

}

void addedge(int i)

{

	int p = find(es[i].u),q = find(es[i].v);

	if(p == q)

	{

		if(find(1) == p)

		{

			if(s.add(val[es[i].u] ^ val[es[i].v] ^ es[i].w))rebuild();

		}

		else

		{

			add(es[i].u,es[i].v,es[i].w);

		}

	}

	else

	{

		if(find(1) == p)

		{

			dfs(es[i].v,val[es[i].u] ^ es[i].w);

		}

		if(find(1) == q)

		{

			dfs(es[i].u,val[es[i].v] ^ es[i].w);

		}

		if(find(1) != p && find(1) != q)

		{

			add(es[i].u,es[i].v,es[i].w);

		}

		f[p] = q;

	}

	return;

}

int main()

{

	freopen("travel.in","r",stdin);

	freopen("travel.out","w",stdout);

	scanf("%d%d%d",&n,&m,&q);

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

	{

		scanf("%d%d%lld",&es[i].u,&es[i].v,&es[i].w);

	}

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

	{

		scanf("%d",&cut[i]);

		tag[cut[i]] = true;

	}

	vis[1] = true;

	rebuild();

	for(int i = 1;i <= n;++i)f[i] = i;

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

	{

		if(tag[i])continue;

		addedge(i);

	}

	for(int i = q;i >= 1;--i)

	{

		ans[i] = t.size() * s.ans;

		addedge(cut[i]);

	}

	ans[0] = t.size() * s.ans;

	for(int i = 0;i <= q;++i)printf("%lld\n",ans[i]);

	fclose(stdin);

	fclose(stdout);

	return 0;

}