2816

思路:

  多个LCT;

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 10005
#define ll long long
int val[maxn];
struct LinkCutTreeType {
int f[maxn],Max[maxn],ch[maxn][],rev[maxn],sta[maxn],top,cnt[maxn];
void updata(int now)
{
Max[now]=val[now];
if(ch[now][]) Max[now]=max(Max[now],Max[ch[now][]]);
if(ch[now][]) Max[now]=max(Max[now],Max[ch[now][]]);
}
void downdata(int now)
{
if(rev[now])
{
rev[now]^=,swap(ch[now][],ch[now][]);
if(ch[now][]) rev[ch[now][]]^=;
if(ch[now][]) rev[ch[now][]]^=;
}
}
bool isroot(int now)
{
return (ch[f[now]][]!=now)&&(ch[f[now]][]!=now);
}
void rotate(int now)
{
int fa=f[now],ffa=f[fa],l=(ch[fa][]==now),r=l^;
if(!isroot(fa)) ch[ffa][ch[ffa][]==fa]=now;
f[now]=ffa,f[fa]=now,ch[fa][l]=ch[now][r],ch[now][r]=fa;
if(ch[fa][l]) f[ch[fa][l]]=fa;updata(fa);
}
void splay(int now)
{
top=,sta[]=now;int fa,ffa;
for(int i=now;!isroot(i);i=f[i]) sta[++top]=f[i];
while(top) downdata(sta[top--]);
while(!isroot(now))
{
fa=f[now],ffa=f[fa];
if(!isroot(fa)) rotate(((ch[ffa][]==fa)^(ch[fa][]==now))?now:fa);
rotate(now);
}
updata(now);
}
void access(int now)
{
for(int i=;now;i=now,now=f[now]) splay(now),ch[now][]=i;
}
void makeroot(int now)
{
access(now),splay(now),rev[now]^=;
}
void cut(int x,int y)
{
makeroot(x),access(y),splay(y);
f[x]=,ch[y][]=,cnt[x]--,cnt[y]--;
}
void link(int x,int y)
{
makeroot(x),f[x]=y,splay(x),cnt[x]++,cnt[y]++;
}
bool iscon(int x,int y)
{
while(f[x]) x=f[x];
while(f[y]) y=f[y];
return x==y;
}
int query(int u,int v)
{
makeroot(u),access(v),splay(v);
return Max[v];
}
};
struct LinkCutTreeType lct[];
int n,m,c,k;
map<ll,int>Map;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
ll Mapped(int u,int v)
{
if(u>v) swap(u,v);
return (ll)u*n*n+v;
}
int main()
{
//freopen("data.txt","r",stdin);
freopen("networkzj.in","r",stdin);
freopen("networkzj.out","w",stdout);
in(n),in(m),in(c),in(k);int u,v,w,op;ll pos,id;
for(int i=;i<=n;i++) in(val[i]);
while(m--) in(u),in(v),in(w),Map[Mapped(u,v)]=w+,lct[w].link(u,v);
while(k--)
{
in(op);
if(op==)
{
in(u),in(val[u]);
for(int i=;i<c;i++) lct[i].splay(u);
}
if(op==)
{
in(u),in(v),in(w),id=Mapped(u,v),pos=Map[id]-;
if(pos<)
{
puts("No such edge.");
continue;
}
if(pos==w)
{
puts("Success.");
continue;
}
if(lct[w].cnt[u]>=||lct[w].cnt[v]>=)
{
puts("Error 1.");
continue;
}
if(lct[w].iscon(u,v))
{
puts("Error 2.");
continue;
}
lct[pos].cut(u,v),lct[w].link(u,v),Map[id]=w+;
puts("Success.");
}
if(op==)
{
in(w),in(u),in(v);
if(!lct[w].iscon(u,v))
{
puts("-1");
continue;
}
printf("%d\n",lct[w].query(u,v));
}
}
return ;
}
05-11 17:31