考场六十分解法
#include<bits/stdc++.h>
#define LL long long
inline void read(LL&a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
inline void write(LL a)
{
if(a<0){a=-a;putchar('-');}
if(a>=10)write(a/10);
putchar(a%10+'0');
}
inline bool get_order()
{
char c=getchar();bool b;
while(c<'a'||c>'z')c=getchar();
if(c=='a')b=true;
else b=false;
while(c>='a'&&c<='z')c=getchar();
return b;
}
#define pmaxn 6001
#define smaxn 210001
struct side
{
LL from,to,len,next;
}s[smaxn];
inline const bool comp(const side&a,const side&b)
{
if(a.len<b.len)return true;
return false;
}
LL n,m,q,k=0;
LL next[pmaxn<<3],to[pmaxn<<3],len[pmaxn<<3];
LL point[pmaxn],d=0,big_side_a;
inline void add(LL a,LL b,LL c)
{
next[++d]=point[a];
point[a]=d;
to[d]=b;
len[d]=c;
}
LL belong[pmaxn];
inline LL check(LL a)
{
if(a==belong[a])return a;
return belong[a]=check(belong[a]);
}
inline void init()
{
d=0;
for(LL i=1;i<=n;i++){belong[i]=i;point[i]=0;}
}
inline LL least_tree()
{
init();
LL group=n-1,i=0;
std::sort(s+1,s+1+k,comp);
while(group)
{
++i;
if(check(s[i].from)==check(s[i].to))continue;
group--;
belong[check(s[i].from)]=s[i].to;
add(s[i].from,s[i].to,s[i].len);
add(s[i].to,s[i].from,s[i].len);
}
return s[i].len;
}
bool vis[pmaxn];
LL ansa,ansb;
inline bool dfs(LL p,LL targ,LL has,bool which)
{
vis[p]=true;
if(p==targ){vis[p]=false;if(which)ansa=has;else ansb=has;return true;}
LL side=point[p],ans=0;
while(side)
{
if(!vis[to[side]])
if(dfs(to[side],targ,std::max(has,len[side]),which)){vis[p]=false;return true;}
side=next[side];
}
vis[p]=false;
return false;
}
int main()
{
read(n);read(m);
LL u,v,l,m1,m2,b1,b2;
for(LL i=1;i<=m;i++)
{
read(u);read(v);read(l);
s[++k].from=u;s[k].to=v;s[k].len=l;
}
memset(vis,false,sizeof(vis));
big_side_a=least_tree();
read(q);
while(q--)
{
if(get_order())
{
read(u);read(v);read(l);
s[++k].from=u;s[k].to=v;s[k].len=l;
if(s[k].len<big_side_a)big_side_a=least_tree();
}
else
{
read(m1);read(m2);
dfs(m1,m2,-1,true);
read(b1);read(b2);
dfs(b1,b2,-1,false);
if(ansa==ansb)puts("Baozika");
else puts("madoka");
}
}
return 0;
}

然后可爱的我只从时间复杂度的方面去想，不考虑常数，然而还是tle了……
#include<bits/stdc++.h>
#define LL long long
inline void read(LL&a)
{
a=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
}
inline void write(LL a)
{
if(a<0){a=-a;putchar('-');}
if(a>=10)write(a/10);
putchar(a%10+'0');
}
inline bool get_order()
{
char c=getchar();bool b;
while(c<'a'||c>'z')c=getchar();
if(c=='a')b=true;
else b=false;
while(c>='a'&&c<='z')c=getchar();
return b;
}
#define pmaxn 6001
#define smaxn 210001
struct side
{
LL from,to,len,next;
}s[smaxn];
inline const bool comp(const side&a,const side&b)
{
if(a.len<b.len)return true;
return false;
}
LL n,m,q,k=0;
LL next[pmaxn<<3],to[pmaxn<<3],len[pmaxn<<3];
LL point[pmaxn],d=0,big_side_a;
inline void add(LL a,LL b,LL c)
{
next[++d]=point[a];
point[a]=d;
to[d]=b;
len[d]=c;
}
LL belong[pmaxn];
inline LL check(LL a)
{
if(a==belong[a])return a;
return belong[a]=check(belong[a]);
}
inline void init()
{
d=0;
for(LL i=1;i<=n;i++){belong[i]=i;point[i]=0;}
}
inline LL least_tree()
{
init();
LL group=n-1,i=0;
std::sort(s+1,s+1+k,comp);
while(group)
{
++i;
if(check(s[i].from)==check(s[i].to))continue;
group--;
belong[check(s[i].from)]=s[i].to;
add(s[i].from,s[i].to,s[i].len);
add(s[i].to,s[i].from,s[i].len);
}
return s[i].len;
}
LL ansa,ansb;
LL son[pmaxn],num[pmaxn],father[pmaxn],top[pmaxn],deep[pmaxn];
inline void dfs1(LL p)
{
son[p]=num[p]=0;
LL side=point[p];
while(side)
{
if(to[side]!=father[p])
{
father[to[side]]=p;
deep[to[side]]=deep[p]+1;
dfs1(to[side]);
num[p]+=num[to[side]];
if(num[to[side]]>num[son[p]])son[p]=to[side];
}
side=next[side];
}
}
LL loc[pmaxn],leaf[pmaxn],rt,wei[pmaxn];
inline void dfs2(LL p,LL tp)
{
top[p]=tp;
leaf[++rt]=wei[p];loc[p]=rt;
if(son[p])dfs2(son[p],tp);
LL side=point[p];
while(side)
{
if(to[side]!=father[p]&&to[side]!=son[p]){wei[to[side]]=len[side];dfs2(to[side],to[side]);}
side=next[side];
}
}
#define root 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
LL big[pmaxn<<2];
inline void update(LL p)
{
big[p]=std::max(big[p<<1],big[p<<1|1]);
}
inline void build(LL p,LL l,LL r)
{
if(l==r){big[p]=leaf[++rt];return ;}
LL mid=l+r>>1;
build(lson);
build(rson);
update(p);
}
inline void modify(LL p,LL l,LL r,LL loc,LL change)
{
if(l==r){big[p]=change;return ;}
LL mid=l+r>>1;
if(loc<=mid)modify(lson,loc,change);
else modify(rson,loc,change);
update(p);
}
inline LL query(LL p,LL l,LL r,LL ll,LL rr)
{
if(l>=ll&&r<=rr)return big[p];
LL mid=l+r>>1,ans=0;
if(mid>=ll)ans=std::max(query(lson,ll,rr),ans);
if(mid+1<=rr)ans=std::max(query(rson,ll,rr),ans);
return ans;
}
inline LL get_ans(LL x,LL y)
{
LL ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])std::swap(x,y);
ans=std::max(query(root,loc[top[x]],loc[x]),ans);
x=father[top[x]];
}
if(deep[x]<deep[y])std::swap(x,y);
ans=std::max(query(root,loc[y],loc[x]),ans);
return ans;
}
int main()
{
read(n);read(m);
LL u,v,l,m1,m2,b1,b2;
for(LL i=1;i<=m;i++)
{
read(u);read(v);read(l);
s[++k].from=u;s[k].to=v;s[k].len=l;
}
big_side_a=least_tree();
deep[1]=0;
dfs1(1);
rt=0;wei[1]=0;
dfs2(1,1);
rt=0;
build(root);
read(q);
while(q--)
{
if(get_order())
{
read(u);read(v);read(l);
s[++k].from=u;s[k].to=v;s[k].len=l;
if(s[k].len<big_side_a)
{
big_side_a=least_tree();
deep[1]=0;
dfs1(1);
rt=0;wei[1]=0;
dfs2(1,1);
rt=0;
build(root);
}
}
else
{
read(m1);read(m2);
ansa=get_ans(m1,m2);
read(b1);read(b2);
ansb=get_ans(b1,b2);
if(ansa==ansb)puts("Baozika");
else puts("madoka");
}
}
return 0;
}
第三篇题解，用的是倍增在线做lca。树剖不能搞满分，因为生成时候的常数实在太大。
感谢Takami同学提供的满分题解
#include <stdio.h>//chenhao
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
int maxh = 12;
const int maxn = 5000;
int n,m;
using namespace std;
int head[maxn],nex[100005<<1],dis[100005<<1],q;
ll w[100005<<1];
int dep[maxn];
struct edge {
int a,b;ll w;
} edges[100005<<1];
int fa[maxn][15];
ll maxx[maxn][15];
inline ll min(ll a,ll b){
return a<b?a:b;
}
inline ll max(ll a,ll b){
return a>b?a:b;
}
//-------------------------辅助类函数-----------------------------
ll read(){
ll num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
bool operator<(const edge &ed1,const edge &ed2) {
return ed1.w<ed2.w;
}
void connect(int x,int y,ll z) {
nex[++q]=head[x],head[x] = q,dis[q] = y;w[q] = z;
nex[++q]=head[y],head[y] = q,dis[q] = x;w[q] = z;
}
void printAns(ll a,ll b) {
if(a!=b) {
cout<<"madoka"<<endl;
} else {
cout<<"Baozika"<<endl;
}
}
int father[maxn];
int find(int a) {
if(father[a]==a) {
return a;
} else {
return find(father[a]);
}
}
void merge(int a,int b) {
int ffa = find(a),ffb = find(b);
father[ffa] = ffb;
}
void dfs(int a) {
//cout<<a;
for(int i = head[a]; i; i=nex[i]) {
int to = dis[i];
if(to!=fa[a][0]) {
dep[to] = dep[a]+1;
fa[to][0] = a;
maxx[to][0] = w[i];
dfs(to);
}
}
}
edge edgeq[6500];
long long rr;

void init(int update) {
if(update) {
for(int i = 0;i<=q;i++) nex[i] = 0;
for(int i = 0;i<=q;i++) dis[i] = 0;
for(int i = 0;i<=n;i++) head[i] = 0;
q = 0;
// sort(edgeq+1,edgeq+1+rr);
for(int i= 1; i<=n; i++)father[i] = i;
int need = n-1;
for(int i = 1; i<=rr&&need; i++) {
if(find(edgeq[i].a)!=find(edgeq[i].b)) {
connect(edgeq[i].a,edgeq[i].b,edgeq[i].w);
need--;
merge(edgeq[i].a,edgeq[i].b);
}
}
}

for(int i = 1;i<=n;i++){
for(int j = 0;j<=maxh;j++){
maxx[i][j] = 0;
fa[i][j] = 0;
}
}
dep[1] = 1;
fa[1][0] = 1;
dfs(1);
for(int h = 1; h<=maxh; h++) {
for(int i = 1; i<=n; i++) {
fa[i][h] = fa[fa[i][h-1]][h-1];
maxx[i][h] = max(maxx[i][h-1],maxx[fa[i][h-1]][h-1]);
}
}

}
ll ans(int a,int b) {
ll ret = 0;
if(dep[a]<dep[b]) {
swap(a,b);
}
for(int i = maxh; i>=0; i--) {
if(dep[fa[a][i]]>=dep[b]) {
ret = max(ret,maxx[a][i]);
a = fa[a][i];
}
}
if(a!=b) {
for(int i = maxh; i>=0; i--) {
if(fa[a][i]!=fa[b][i]) {
ret = max(ret,maxx[a][i]);
ret = max(ret,maxx[b][i]);
a = fa[a][i];
b = fa[b][i];
}
}
ret = max(ret,maxx[a][0]);
ret = max(ret,maxx[b][0]);
} else {
return ret;
}
return ret;
}
void addLine(int a,int b,ll z)
{
edge ed;
ed.a = a,ed.b = b,ed.w = z;
int index = upper_bound(edgeq+1,edgeq+rr+1,ed)-edgeq;
for(int i = rr;i>=index;i--){
edgeq[i+1] = edgeq[i];
}
edgeq[index] = ed;
rr++;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i<=m; i++)
{
int x=read(),y=read();ll z=read();
edges[i].a =x,edges[i].b=y,edges[i].w=z;
}
sort(edges+1,edges+1+m);
for(int i= 1; i<=n; i++)father[i] = i;
int need = n-1;
for(int i = 1; i<=m&&need; i++) {
if(find(edges[i].a)!=find(edges[i].b)) {
connect(edges[i].a,edges[i].b,edges[i].w);
edgeq[++rr] = edges[i];
need--;
merge(edges[i].a,edges[i].b);
}
}
init(0);
int tt;
scanf("%d",&tt);
int updated = 1;
for(int i = 1; i<=tt; i++) {
char str[10];
cin>>str;
if(str[0]=='g') {
int x,y,z,w;
if(!updated) init(1);
updated = 1;
x=read(),y=read(),z=read(),w=read();
printAns(ans(x,y),ans(z,w));
} else {
updated = 0;
ll x=read(),y=read(),z=read();
if(z!=998244353)
addLine(x,y,z);
}
}
return 0;
}