題目大意：給定一張帶權無向圖，每次刪去一條邊並詢問從點1出發走一條路徑可以走出多少種不同的邊權異或和
刪邊不好做 首先倒著做 把刪邊改成加邊
回憶2115那題的做法 我們可以把一條路徑的異或和拆成一條簡單路徑和一些環的異或值
2115是求最大異或和 這個題是求異或和的個數
因此我們維護兩個集合 環的異或和集合和路徑的異或和集合
這裡說的路徑包括原地不動 即從1到1的路徑
如果一個環的異或和能被其它環線性表示 那麼這個環對答案顯然沒有貢獻 於是這個環就可以從集合中刪掉
因此環的集合要維護一個線性基的形式
如果一條路徑的異或和異或上一些環之後等於另一條路徑，這條路徑對答案顯然沒有貢獻
因此路徑的集合需要對線性基消元，且保證消元後不重
設環的集合大小為R，路徑的集合大小為P，那麼答案就是P*2^R-1
不過這題需要動態維護- - 實現起來就比較麻煩了- - 我細說吧- -
首先思想是維護一棵以1為根的生成樹，將樹上的路徑都視作路徑，每條非樹邊對應一個環
路徑集合的去重利用set來完成
每添加一條邊，步驟如下：
如果邊的兩端點都被訪問過，就把這條邊所在環的異或值扔進線性基中消元
如果此次消元後線性基被更新，那麼將set中所有的路徑取出，對本次更新的線性基消元後再放回去
如果只有一端點被訪問過，那麼就深搜另一端點所在聯通塊，標記訪問節點
對於深搜到的每個點，將1號節點到該節點的路徑的異或和對線性基消元後扔進set
對於深搜到的每條非樹邊，扔進線性基中消元並更新set中的元素
時間復雜度O(nlognlogk) 其中k是最大的邊權
#include
#include
#include
#include
#include
#define M 20200
using namespace std;
struct edge{
int x,y;
long long z;
}edges[M];
struct abcd{
int to,next;
long long f;
}table[M<<1];
int head[M],tot=1;
int n,m,q,cnt;
bool _v[M],v[M];
int queries[M];
long long a[M],ans[M],linear_bases[64];
set s;
void Add(int x,int y,long long z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
void Gauss_Elimination(long long x)
{
int i;
for(i=62;~i;i--)
if( (x^linear_bases[i])::iterator it;
for(it=s.begin();it!=s.end();it++)
stack[++top]=*it;
for(s.clear();top;top--)
s.insert( min(stack[top],stack[top]^x) );
}
void DFS(int x,int from)
{
int i;
v[x]=1;
a[x]=a[table[from^1].to]^table[from].f;
long long temp=a[x];
for(i=62;~i;i--)
temp=min(temp,temp^linear_bases[i]);
s.insert(temp);
for(i=head[x];i;i=table[i].next)
if(i^from^1)
{
if(!v[table[i].to])
DFS(table[i].to,i);
else
Gauss_Elimination(table[i].f^a[x]^a[table[i].to]);
}
}
void Insert(int id)
{
int x=edges[id].x;
int y=edges[id].y;
Add(x,y,edges[id].z);
Add(y,x,edges[id].z);
if(v[x]&&v[y])www.2cto.com
Gauss_Elimination(edges[id].z^a[x]^a[y]);
else if(v[x])
DFS(y,tot-1);
else if(v[y])
DFS(x,tot);
}
int main()
{
int i,x,y;
long long z;
cin>>n>>m>>q;
for(i=1;i<=m;i++)
{
#ifdef ONLINE_JUDGE
scanf("%d%d%lld",&x,&y,&z);
#else
scanf("%d%d%I64d",&x,&y,&z);
#endif
edges[i].x=x;
edges[i].y=y;
edges[i].z=z;
}
for(i=1;i<=q;i++)
{
scanf("%d",&queries[i]);
_v[queries[i]]=true;
}
s.insert(0);
v[1]=1;
for(i=1;i<=m;i++)
if(!_v[i])
Insert(i);
for(i=q;i;i--)
{
ans[i]=s.size()*(1ll<
