搞了一上午LCT，真是累死了……
以前总觉得LCT高大上不好学不好打，今天打了几遍感觉还可以嘛= =反正现在的水平应付不太难的LCT题也够用了，就这样好了，接下来专心搞网络流。
话说以前一直YY不出来LCT怎么维护边权，多谢sxysxy告诉我要添虚点来把边权转化为点权，感激不尽……
言归正传。
LCT模板题嘛……
区间乘和区间加一遍写对，感觉费了好多rp……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((x)==(x)->p->ch[1])
using namespace std;
typedef unsigned uint;
const int maxn=;
const uint M=51061u;
struct node{
uint data,sm,a,b;
int size;
node *ch[],*p;
bool rev;
node(uint d=0u):data(d),sm(d),a(1u),b(0u),size(),rev(false){}
void add(uint d){
sm+=(uint)size%M*d%M;sm%=M;
data+=d;data%=M;
b+=d;b%=M;
}
void mul(uint d){
sm*=d;sm%=M;
data*=d;data%=M;
b*=d;b%=M;
a*=d;a%=M;
}
void pushdown(){
if(rev){
ch[]->rev^=true;
ch[]->rev^=true;
swap(ch[],ch[]);
rev=false;
}
if(a!=){
ch[]->mul(a);
ch[]->mul(a);
a=1u;
}
if(b){
ch[]->add(b);
ch[]->add(b);
b=0u;
}
}
void refresh(){
size=ch[]->size+ch[]->size+;
sm=ch[]->sm+ch[]->sm;sm%=M;sm+=data;sm%=M;
}
}nodes[maxn],*null=nodes;
void dfs(int);
void add(node*,node*,uint);
void mul(node*,node*,uint);
uint qsum(node*,node*);
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
void splay(node*);
void rot(node*,int);
vector<int>G[maxn];
int n,m,prt[maxn]={},x,y;
uint d;
char c;
int main(){
freopen("nt2012_wym_tree.in","r",stdin);
freopen("nt2012_wym_tree.out","w",stdout);
null->ch[]=null->ch[]=null->p=null;
null->size=;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs();
for(int i=;i<=n;i++){
nodes[i]=node();
nodes[i].ch[]=nodes[i].ch[]=null;
nodes[i].p=nodes+prt[i];
}
while(m--){
scanf(" %c%d%d",&c,&x,&y);
if(c=='+'){
scanf("%u",&d);
add(nodes+x,nodes+y,d);
}
else if(c=='-'){
cut(nodes+x,nodes+y);
scanf("%d%d",&x,&y);
link(nodes+x,nodes+y);
}
else if(c=='*'){
scanf("%u",&d);
mul(nodes+x,nodes+y,d);
}
else if(c=='/')printf("%u\n",qsum(nodes+x,nodes+y));
}
return ;
}
void dfs(int x){
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=prt[x]){
prt[G[x][i]]=x;
dfs(G[x][i]);
}
}
void add(node *x,node *y,uint d){
makeroot(x);
access(y)->add(d);
}
void mul(node *x,node *y,uint d){
makeroot(x);
access(y)->mul(d);
}
uint qsum(node *x,node *y){
makeroot(x);
return access(y)->sm;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
(y=x)->refresh();
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
x->p=null;
y->ch[]=null;
y->refresh();
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
x->refresh();
y->refresh();
}
也是LCT维护森林连通性的模板题。
话说一开始读错题了，以为是一般图，就写了一发分治并查集，然后发现LCT又好写又跑得快……
分治并查集的代码长度亮了……
分治并查集：
/**************************************************************
Problem: 2049
User: hzoier
Language: C++
Result: Accepted
Time:4988 ms
Memory:58572 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int maxn=,maxm=;
inline int randint(){
static int a=,b=,c=,x=,p=;
x=a*x*x+b*x+c;x%=p;x+=p;
return x%=p;
}
void addedge(int,int,int);
void addquery(int,int,int);
void solve(int,int,int);
int findroot(int);
void mergeset(int,int,vector<int>&);
int prt[maxn];
map<pair<int,int>,int>mp;
vector<int>u[maxm<<],v[maxm<<],stk[maxm<<];
int qu[maxm<<]={},qv[maxm<<];
int n,m,x,y,s,t;
char c[];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)prt[i]=i;
for(int i=;i<=m;i++){
scanf("%s%d%d",c,&x,&y);
if(x>y)swap(x,y);
if(*c=='C'){
if(!mp.count(make_pair(x,y)))mp[make_pair(x,y)]=i;
}
else if(*c=='D'){
s=mp[make_pair(x,y)];
t=i;
addedge(,m,);
mp.erase(make_pair(x,y));
}
else{
t=i;
addquery(,m,);
}
}
t=m;
for(map<pair<int,int>,int>::iterator it=mp.begin();it!=mp.end();it++){
x=it->first.first;
y=it->first.second;
s=it->second;
addedge(,m,);
}
solve(,m,);
return ;
}
void addedge(int l,int r,int rt){
if(s<=l&&t>=r){
u[rt].push_back(x);
v[rt].push_back(y);
return;
}
int mid=(l+r)>>;
if(s<=mid)addedge(l,mid,rt<<);
if(t>mid)addedge(mid+,r,rt<<|);
}
void addquery(int l,int r,int rt){
qu[rt]|=x;
if(l==r){
qv[rt]=y;
return;
}
int mid=(l+r)>>;
if(t<=mid)addquery(l,mid,rt<<);
else addquery(mid+,r,rt<<|);
}
void solve(int l,int r,int rt){
if(!qu[rt])return;
for(int i=;i<(int)u[rt].size();i++)mergeset(u[rt][i],v[rt][i],stk[rt]);
if(l==r)printf(findroot(qu[rt])==findroot(qv[rt])?"Yes\n":"No\n");
else{
int mid=(l+r)>>;
solve(l,mid,rt<<);
solve(mid+,r,rt<<|);
}
if(!stk[rt].empty())for(int i=(int)stk[rt].size()-;i>=;i--)prt[stk[rt][i]]=stk[rt][i];
}
void mergeset(int x,int y,vector<int>&a){
x=findroot(x);y=findroot(y);
if(x==y)return;
if(randint()&)swap(x,y);
prt[x]=y;
a.push_back(x);
}
int findroot(int x){
while(prt[x]!=x)x=prt[x];
return x;
}
LCT：
/**************************************************************
Problem: 2049
User: hzoier
Language: C++
Result: Accepted
Time:1656 ms
Memory:976 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=;
struct node{
bool rev;
node *ch[],*p;
node():rev(false){}
void pushdown(){
if(!rev)return;
ch[]->rev^=true;
ch[]->rev^=true;
swap(ch[],ch[]);
rev=false;
}
}nodes[maxn],*null=nodes;
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *findroot(node*);
void splay(node*);
void rot(node*,int);
int n,m,x,y;
char c[];
int main(){
null->ch[]=null->ch[]=null->p=null;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)nodes[i].ch[]=nodes[i].ch[]=nodes[i].p=null;
while(m--){
scanf("%s%d%d",c,&x,&y);
if(*c=='C')link(nodes+x,nodes+y);
else if(*c=='D')cut(nodes+x,nodes+y);
else printf(findroot(nodes+x)==findroot(nodes+y)?"Yes\n":"No\n");
}
return ;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
y=x;
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
y->ch[]=null;
x->p=null;
}
node *findroot(node *x){
access(x);
splay(x);
while(x->pushdown(),x->ch[]!=null)x=x->ch[];
return x;
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
}
只有加边的动态MST，LCT维护即可。
注意加虚点来维护边权。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=;
struct node{
int data,mx,pos;
node *ch[],*p;
bool rev;
node(int d):data(d),mx(d),pos(-),rev(false){}
void pushdown(){
if(!rev)return;
if(pos!=-)pos^=;
ch[]->rev^=true;
ch[]->rev^=true;
swap(ch[],ch[]);
rev=false;
}
void refresh(){
mx=data;
pos=-;
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
}
}*null=new node(-);
node *newnode(int);
node *access(node*);
void makeroot(node*);
void cut(node*,node*);
void link(node*,node*);
node *getroot(node*);
node *getmax(node*,node*);
void splay(node*);
void rot(node*,int);
map<node*,pair<node*,node*> >mp;
node *iter[maxn];
int n,m,cnt=,x,y,w,ans=;
node *tmp;
int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
null->ch[]=null->ch[]=null->p=null;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)iter[i]=newnode(-);
while(m--){
scanf("%d%d%d",&x,&y,&w);
if(getroot(iter[x])!=getroot(iter[y])){
tmp=newnode(w);
mp[tmp]=make_pair(iter[x],iter[y]);
link(tmp,iter[x]);
link(tmp,iter[y]);
ans+=w;
cnt++;
}
else{
node *tmp=getmax(iter[x],iter[y]);
if(tmp->data>w){
ans-=tmp->data;
cut(tmp,mp[tmp].first);
cut(tmp,mp[tmp].second);
tmp->data=w;
mp[tmp]=make_pair(iter[x],iter[y]);
link(tmp,iter[x]);
link(tmp,iter[y]);
ans+=w;
}
}
if(cnt==n-)printf("%.1lf\n",(double)ans/2.0);
else printf("0\n");
}
return ;
}
node *newnode(int d){
node *x=new node(d);
x->ch[]=x->ch[]=x->p=null;
return x;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
(y=x)->refresh();
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
x->p=null;
y->ch[]=null;
y->refresh();
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
node *getroot(node *x){
x=access(x);
while(x->pushdown(),x->ch[]!=null)x=x->ch[];
splay(x);
return x;
}
node *getmax(node *x,node *y){
makeroot(x);
x=access(y);
while(x->pushdown(),x->pos!=-)x=x->ch[x->pos];
return x;
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
x->refresh();
y->refresh();
}
只有删边的动态MST，时光倒流之后就转成了只有加边的动态MST，仍然LCT维护。
话说初始MST一开始我是直接用LCT构建的，后来一看怎么我跑得这么慢才发现大家都是用的Kruskal……然后写了一发Prim，发现仍然很慢……= =
直接LCT：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=;
template<class T>inline void readint(T &x){
static int c=;
x=;
while(c!=EOF&&(c<''||c>''))c=getchar();
if(c==EOF)return;
while(c>=''&&c<=''){
x=(x<<)+(x<<)+(c^);
c=getchar();
}
}
struct node{
int data,mx,pos;
node *ch[],*p;
bool rev;
node(int d=-):data(d),mx(d),pos(-),rev(false){}
void pushdown(){
if(!rev)return;
if(pos!=-)pos^=;
ch[]->rev^=true;
ch[]->rev^=true;
swap(ch[],ch[]);
rev=false;
}
void refresh(){
mx=data;
pos=-;
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
}
}nodes[maxn<<],*null=nodes,*ptr;
struct A{int tp,x,y,w;}a[maxn<<];
node *newnode(int);
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *getroot(node*);
node *getmax(node*,node*);
void splay(node*);
void rot(node*,int);
int n,m,q,ans[maxn<<];
map<node*,pair<node*,node*> >mp;
map<pair<int,int>,int>e;
int main(){
freopen("tube_strong.in","r",stdin);
freopen("tube_strong.out","w",stdout);
null->ch[]=null->ch[]=null->p=null;
readint(n);
readint(m);
readint(q);
ptr=nodes+n;
for(int i=;i<=n;i++)nodes[i].ch[]=nodes[i].ch[]=nodes[i].p=null;
while(m--){
int x,y,w;
readint(x);
readint(y);
readint(w);
if(x>y)swap(x,y);
e[make_pair(x,y)]=w;
}
m=q;
for(int i=;i<=m;i++){
readint(a[i].tp);
readint(a[i].x);
readint(a[i].y);
if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
if(a[i].tp==){
a[i].w=e[make_pair(a[i].x,a[i].y)];
e.erase(make_pair(a[i].x,a[i].y));
}
}
for(map<pair<int,int>,int>::iterator it=e.begin();it!=e.end();it++){
a[++m].tp=;
a[m].x=it->first.first;
a[m].y=it->first.second;
a[m].w=it->second;
}
for(int i=m;i;i--){
int x=a[i].x,y=a[i].y,w=a[i].w;
if(a[i].tp==)ans[i]=getmax(nodes+x,nodes+y)->data;
else{
node *tmp;
if(getroot(nodes+x)!=getroot(nodes+y)){
tmp=newnode(w);
link(tmp,nodes+x);
link(tmp,nodes+y);
mp[tmp]=make_pair(nodes+x,nodes+y);
}
else{
tmp=getmax(nodes+x,nodes+y);
if(tmp->data>w){
cut(tmp,mp[tmp].first);
cut(tmp,mp[tmp].second);
tmp->data=w;
link(tmp,nodes+x);
link(tmp,nodes+y);
mp[tmp]=make_pair(nodes+x,nodes+y);
}
}
}
}
for(int i=;i<=m;i++)if(a[i].tp==)printf("%d\n",ans[i]);
return ;
}
node *newnode(int d){
*++ptr=node(d);
ptr->ch[]=ptr->ch[]=ptr->p=null;
return ptr;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
(y=x)->refresh();
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
y->ch[]=null;
x->p=null;
y->refresh();
}
node *getroot(node *x){
x=access(x);
while(x->pushdown(),x->ch[]!=null)x=x->ch[];
splay(x);
return x;
}
node *getmax(node *x,node *y){
makeroot(x);
x=access(y);
while(x->pushdown(),x->pos!=-)x=x->ch[x->pos];
splay(x);
return x;
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
x->refresh();
y->refresh();
}
Prim：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=;
template<class T>inline void readint(T &x){
static int c=;
x=;
while(c!=EOF&&(c<''||c>''))c=getchar();
if(c==EOF)return;
while(c>=''&&c<=''){
x=(x<<)+(x<<)+(c^);
c=getchar();
}
}
struct node{
int data,mx,pos;
node *ch[],*p;
bool rev;
node(int d=-):data(d),mx(d),pos(-),rev(false){}
void pushdown(){
if(!rev)return;
if(pos!=-)pos^=;
ch[]->rev^=true;
ch[]->rev^=true;
swap(ch[],ch[]);
rev=false;
}
void refresh(){
mx=data;
pos=-;
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
}
}nodes[maxn<<],*null=nodes,*ptr;
struct oper{int tp,x,y,w;}a[maxn];
struct A{
int x,dis;
A(int x,int dis):x(x),dis(dis){}
bool operator<(const A &a)const{return dis>a.dis;}
};
void Prim();
node *newnode(int);
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *getmax(node*,node*);
void splay(node*);
void rot(node*,int);
vector<int>G[maxn],W[maxn];
int dis[maxn],prt[maxn]={};
bool vis[maxn]={false};
int n,m,q,ans[maxn];
map<node*,pair<node*,node*> >mp;
map<pair<int,int>,int>e;
int main(){
freopen("tube_strong.in","r",stdin);
freopen("tube_strong.out","w",stdout);
null->ch[]=null->ch[]=null->p=null;
readint(n);
readint(m);
readint(q);
ptr=nodes+n;
for(int i=;i<=n;i++)nodes[i].ch[]=nodes[i].ch[]=nodes[i].p=null;
while(m--){
int x,y,w;
readint(x);
readint(y);
readint(w);
if(x>y)swap(x,y);
e[make_pair(x,y)]=w;
}
m=q;
for(int i=;i<=m;i++){
readint(a[i].tp);
readint(a[i].x);
readint(a[i].y);
if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
if(a[i].tp==){
a[i].w=e[make_pair(a[i].x,a[i].y)];
e.erase(make_pair(a[i].x,a[i].y));
}
}
for(map<pair<int,int>,int>::iterator it=e.begin();it!=e.end();it++){
G[it->first.first].push_back(it->first.second);
W[it->first.first].push_back(it->second);
G[it->first.second].push_back(it->first.first);
W[it->first.second].push_back(it->second);
}
Prim();
for(int i=m;i;i--){
int x=a[i].x,y=a[i].y,w=a[i].w;
if(a[i].tp==)ans[i]=getmax(nodes+x,nodes+y)->data;
else{
node *tmp=getmax(nodes+x,nodes+y);
if(tmp->data>w){
cut(tmp,mp[tmp].first);
cut(tmp,mp[tmp].second);
tmp->data=w;
link(tmp,nodes+x);
link(tmp,nodes+y);
mp[tmp]=make_pair(nodes+x,nodes+y);
}
}
}
for(int i=;i<=m;i++)if(a[i].tp==)printf("%d\n",ans[i]);
return ;
}
void Prim(){
fill(dis+,dis+n+,0x3f3f3f3f);
priority_queue<A>q;
dis[]=;
q.push(A(,));
while(!q.empty()){
int x=q.top().x;
q.pop();
if(vis[x])continue;
vis[x]=true;
for(int i=;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&dis[G[x][i]]>W[x][i]){
dis[G[x][i]]=W[x][i];
prt[G[x][i]]=x;
q.push(A(G[x][i],W[x][i]));
}
}
for(int i=;i<=n;i++){
node *x=newnode(dis[i]);
x->p=nodes+prt[i];
nodes[i].p=x;
mp[x]=make_pair(nodes+min(prt[i],i),nodes+max(prt[i],i));
}
}
node *newnode(int d){
*++ptr=node(d);
ptr->ch[]=ptr->ch[]=ptr->p=null;
return ptr;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
(y=x)->refresh();
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
y->ch[]=null;
x->p=null;
y->refresh();
}
node *getmax(node *x,node *y){
makeroot(x);
x=access(y);
while(x->pushdown(),x->pos!=-)x=x->ch[x->pos];
splay(x);
return x;
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
x->refresh();
y->refresh();
}
话说这两份代码bzoj上都T到死，也是没谁了……
这才是真·动态MST……
听说有个算法叫CDQ重构图，然而太神了并不能看懂，于是乎写了一发对时间分治+LCT，常数大如dog，成功被卡掉……
反正各种卡常都过不去，我还是贴没卡常的代码好了……
/**************************************************************
Problem: 2001
User: hzoier
Language: C++
Result: Time_Limit_Exceed
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=,maxm=;
struct node{
int data,mx,pos;
node *ch[],*p;
bool rev;
node(int d=-):data(d),mx(d),pos(-),rev(false){}
void pushdown(){
if(!rev)return;
if(pos!=-)pos^=;
ch[]->rev^=;
ch[]->rev^=;
swap(ch[],ch[]);
rev=false;
}
void refresh(){
mx=data;
pos=-;
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
if(ch[]->mx>mx){
mx=ch[]->mx;
pos=;
}
}
}nodes[maxn<<],*null=nodes,*ptr=nodes;
struct edge{int x,y,t,w;}e[maxm];
struct A{
node *x,*u,*v;
int w;
A(node *x,node *u,node *v,int w):x(x),u(u),v(v),w(w){}
};
void addedge(int,int,int);
void solve(int,int,int,long long);
node *newnode(int);
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *getmax(node*,node*);
node *getroot(node*);
void splay(node*);
void rot(node*,int);
vector<int>u[maxm<<],v[maxm<<],w[maxm<<];
map<node*,pair<node*,node*> >mp;
int n,m,q,s,t,k,x,y,z;
node *tmp;
int main(){
null->ch[]=null->ch[]=null->p=null;
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)newnode(-);
for(int i=;i<n;i++){
tmp=newnode();
link(tmp,nodes+i);
link(tmp,nodes+i+);
mp[tmp]=make_pair(nodes+i,nodes+i+);
}
for(int i=;i<=m;i++){
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
e[i].t=;
}
for(int i=;i<=q;i++){
scanf("%d%d",&k,&z);
x=e[k].x;y=e[k].y;
s=e[k].t;t=i-;
swap(e[k].w,z);
if(t)addedge(,q,);
e[k].t=i;
}
for(int i=;i<=m;i++){
s=e[i].t;t=q;
x=e[i].x;y=e[i].y;z=e[i].w;
addedge(,q,);
}
solve(,q,,(long long)(n-)*);
return ;
}
void addedge(int l,int r,int rt){
if(s<=l&&t>=r){
u[rt].push_back(x);
v[rt].push_back(y);
w[rt].push_back(z);
return;
}
int mid=(l+r)>>;
if(s<=mid)addedge(l,mid,rt<<);
if(t>mid)addedge(mid+,r,rt<<|);
}
void solve(int l,int r,int rt,long long ans){
vector<A>stk;
for(int i=;i<(int)u[rt].size();i++){
tmp=getmax(nodes+u[rt][i],nodes+v[rt][i]);
if(tmp->data>w[rt][i]){
stk.push_back(A(tmp,mp[tmp].first,mp[tmp].second,tmp->data));
cut(tmp,mp[tmp].first);
cut(tmp,mp[tmp].second);
ans-=tmp->data;
mp[tmp]=make_pair(nodes+u[rt][i],nodes+v[rt][i]);
tmp->data=w[rt][i];
link(tmp,nodes+u[rt][i]);
link(tmp,nodes+v[rt][i]);
ans+=w[rt][i];
}
}
if(l==r)printf("%lld\n",ans);
else{
int mid=(l+r)>>;
solve(l,mid,rt<<,ans);
solve(mid+,r,rt<<|,ans);
}
if(!stk.empty())for(int i=(int)stk.size()-;i>=;i--){
cut(stk[i].x,mp[stk[i].x].first);
cut(stk[i].x,mp[stk[i].x].second);
mp[stk[i].x]=make_pair(stk[i].u,stk[i].v);
stk[i].x->data=stk[i].w;
link(stk[i].x,stk[i].u);
link(stk[i].x,stk[i].v);
}
}
node *newnode(int d){
*++ptr=node(d);
ptr->ch[]=ptr->ch[]=ptr->p=null;
return ptr;
}
node *access(node *x){
node *y=null;
while(x!=null){
splay(x);
x->ch[]=y;
(y=x)->refresh();
x=x->p;
}
return y;
}
void makeroot(node *x){
access(x);
splay(x);
x->rev^=true;
}
void link(node *x,node *y){
makeroot(x);
x->p=y;
}
void cut(node *x,node *y){
makeroot(x);
access(y);
splay(y);
y->ch[]=null;
x->p=null;
y->refresh();
}
node *getmax(node *x,node *y){
makeroot(x);
x=access(y);
while(x->pushdown(),x->pos!=-)x=x->ch[x->pos];
splay(x);
return x;
}
node *getroot(node *x){
x=access(x);
while(x->pushdown(),x->ch[]!=null)x=x->ch[];
splay(x);
return x;
}
void splay(node *x){
x->pushdown();
while(!isroot(x)){
if(!isroot(x->p))x->p->p->pushdown();
x->p->pushdown();
x->pushdown();
if(isroot(x->p)){
rot(x->p,dir(x)^);
break;
}
if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^);
else rot(x->p,dir(x)^);
rot(x->p,dir(x)^);
}
}
void rot(node *x,int d){
node *y=x->ch[d^];
x->ch[d^]=y->ch[d];
if(y->ch[d]!=null)y->ch[d]->p=x;
y->p=x->p;
if(!isroot(x))x->p->ch[dir(x)]=y;
y->ch[d]=x;
x->p=y;
x->refresh();
y->refresh();
}
话说写这题的时候调了半天，最后发现我pushdown的时候忘了交换左右儿子，真是智障……
感觉这几道题还好吧……每道题都是重新打的LCT(虽然调不出来的时候会拿出上一题的代码手动FC……)，感觉考试考到的话模板应该是打不错了。
LCT真是累啊……算了我接下来还是专心搞网络流好了……