UOJ 274 温暖会指引我们前进 - LCT

Solution

更新掉路径上温暖度最小的边就可以了~

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define rd read()

 using namespace std;

 const int N = 4e5 + ;

 const int inf = ~0U >> ;

 int n, m, fa[N];

 struct edge {

     int u, v, t, w;

 }e[N];

 int read() {

     int X = , p = ; char c = getchar();

     for (; c > '' || c < ''; c = getchar())

         if (c == '-') p = -;

     for (; c >= '' && c <= ''; c = getchar())

         X = X *  + c - '';

     return X * p;

 }

 int anc(int x) {

     return fa[x] == x ? x : fa[x] = anc(fa[x]);

 }

 namespace LCT {

     int f[N], ch[N][], val[N], mn[N], tun[N];

     ll sum[N];

 #define lc(x) ch[x][0]

 #define rc(x) ch[x][1]

     int isroot(int x) {

         return lc(f[x]) != x && rc(f[x]) != x;

     }

     int get(int x) {

         return rc(f[x]) == x;

     }

     void up(int x) {

         mn[x] = val[x];

         sum[x] = e[val[x]].t;

         if (e[mn[lc(x)]].w < e[mn[x]].w) mn[x] = mn[lc(x)];

         if (e[mn[rc(x)]].w < e[mn[x]].w) mn[x] = mn[rc(x)];

         if (lc(x)) sum[x] += sum[lc(x)];

         if (rc(x)) sum[x] += sum[rc(x)];

     }

     void rev(int x) {

         swap(lc(x), rc(x));

         tun[x] ^= ;

     }

     void pushdown(int x) {

         if (tun[x]) {

             if (lc(x)) rev(lc(x));

             if (rc(x)) rev(rc(x));

             tun[x] = ;

         }

     }

 int st[N], tp;

     void pd(int x) {

         while (!isroot(x)) {

             st[++tp] = x;

             x = f[x];

         }

         pushdown(x);

         while (tp) pushdown(st[tp--]);

     }

     void rotate(int x) {

         int old = f[x], oldf = f[old], son = ch[x][get(x) ^ ];

         if (!isroot(old)) ch[oldf][get(old)] = x;

         ch[x][get(x) ^ ] = old;

         ch[old][get(x)] = son;

         f[old] = x; f[x] = oldf; f[son] = old;

         up(old); up(x);

     }

     void splay(int x) {

         pd(x);

         for (; !isroot(x); rotate(x))

             if (!isroot(f[x]))

                 rotate(get(f[x]) == get(x) ? f[x] : x);

     }

     void access(int x) {

         for (int y = ; x; y = x, x = f[x])

             splay(x), ch[x][] = y, up(x);

     }

     int findr(int x) {

         access(x); splay(x);

         while (lc(x)) pushdown(x), x = lc(x);

         return x;

     }

     void mroot(int x) {

         access(x); splay(x); rev(x);

     }

     void split(int x, int y) {

         mroot(x); access(y); splay(y);

     }

     void link(int x, int y) {

         mroot(x);

         f[x] = y;

     }

     void cut(int x, int y) {

         split(x, y);

         f[x] = ch[y][] = ;

     }

 }

 using namespace LCT;

 int main()

 {

     e[].w = inf;

     n = rd; m = rd;

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

         fa[i] = i;

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

         val[i + n] = i;

     char op[];

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

         scanf("%s", op);

         if (op[] == 'f') {

             int id = rd + ;

             e[id].u = rd + ;

             e[id].v = rd + ;

             e[id].w = rd;

             e[id].t = rd;

             int x = e[id].u, y = e[id].v;

             if (anc(x) != anc(y)) {

                 link(id + n, x);

                 link(id + n, y);

                 x = anc(x); y = anc(y);

                 fa[x] = y;

             }

             else {

                 split(x, y);

                 int t = mn[y];

                 if (e[id].w < e[t].w)

                     continue;

                 cut(t + n, e[t].u);

                 cut(t + n, e[t].v);

                 link(id + n, e[id].u);

                 link(id + n, e[id].v);

             }

         }

         else if(op[] == 'm') {

             int x = rd + , y = rd + ;

             if (anc(x) != anc(y)) {

                 puts("-1"); continue;

             }

             if (x == y) {puts(""); continue;}

             split(x, y);

             printf("%lld\n", sum[y]);

         }

         else {

             int id = rd + ;

             e[id].t = rd;

             mroot(id + n);

         }

     }

 }