[Codeforces 603E]Pastoral Oddities

首先，當一個連通塊包含偶數個點的時候，我們一定可以構造出某種子圖使得連通塊內每一個點都連到奇數條邊
方法如下：
度數為偶數的點一定是偶數個，因此隨便將它們兩兩配對並連出一條路，路徑和路徑之間可以重疊
接著，將所有被路徑經過奇數次的邊從圖上刪除
你會發現剩下的邊組成的子圖即為所求

因此，只要整張圖被分成若干個偶數大小的連通塊就好了
一開始，總共有$N$個大小為$1$的連通塊

接著，會有一條一條的邊加入，可能會把連通塊連接起來
可以發現，連通塊互相連接的時候，奇數大小的連通塊只會減少，不會增加
證明：
$奇+奇\rightarrow偶$：減少$2$
$奇+偶\rightarrow奇$：不變
$偶+偶\rightarrow偶$：不變

因此，當目前加入的邊還沒有辦法形成滿足條件的子圖時，盡量把連通塊接起來是好選擇(?)

再來是討論怎麼最小化最大邊的權值
我們可以將邊由大到小開始從圖上移除，當分裂出奇數大小的連通塊時，這條邊的權值即為所求

怎麼做連通塊的分裂和合併操作？

可以發現，當某個連通塊內形成環時，直接將環上的最大邊刪除並不會影響正確性 (不減損連通性，將邊由大到小開始從圖上移除時也是最先刪除這條邊，不如現在就把它刪除)
因此，我們形同維護了多棵樹組成的森林！

這裡用到了一種專門對樹設計的資料結構：$link-cut\ tree$
它會將每棵樹剖分成好幾條鏈，每條鏈會用$splay\ tree$來維護，每棵$splay\ tree$多維護了父節點，但其父節點的兩個小孩不一定有它
$link-cut\ tree$可以支持以下操作：
Node *Access(Node *o)：將某點到樹根的路徑合成一條鏈，並適時的斷開一些其他鏈。可以證明，這樣斷開、合成的次數均攤$O(1)$，考慮$splay\ tree$的分裂合併複雜度後變為$O(\log N)$

對，主要就是這個操作，若我們利用懶惰標記讓$splay\ tree$支持$O(1)$反轉操作，還可以多一個功能！
void SetRoot(Node *o)：將樹根設成$o$ (實作上可以先Access(o)，然後反轉整條鏈)

透過組合這兩個功能，我們可以進行很多不可思議的操作！

同時，我們可以在不影響時間複雜度的情況下順便維護一些資訊
對於本題，可以考慮維護以下資訊：
1. w：子樹中不在同一條鏈的總大小
2. sz：$splay\ tree$中每個子節點包含的子樹大小總和

這樣一來，以下操作得以實現，時間複雜度均為$O(\log N)$
小提醒：實作上把邊當作點來看待會方便許多，如$a$、$b$間連了一條邊$e$，當作$a$和$e$相連、$e$和$b$相連
1. bool IsConnected(Node *a,Node *b)：詢問$a$、$b$是否在同一棵樹內
2. void Link(Node *a,Node *b)：在$a$、$b$間新增一條邊把兩棵樹接起來，形成一棵完整的樹
3. void Cut(Node *a,Node *b)：刪除$a$、$b$兩點間的邊，使一棵樹分裂成兩棵樹
4. Node *PathMax(Node *a,Node *b)：取得$a$到$b$這條路徑上權值最大的邊
5. Access(o)->sz：取得$o$點所在的樹的大小

因此，整個流程大概是這樣：
讀進一條邊的資訊
判斷是否形成一個環
　是：搞分裂，刪除環上最大權邊
　否：將兩棵樹接起來
判斷是否還有奇數大小的連通塊 (其實都是樹)
　是：都嫌邊不夠多了，幹嘛刪邊
　否：挑出圖中的最大權邊，刪除看看是否分裂出奇數大小的連通塊
　　是：這條邊不能刪，加回去
　　否：繼續刪邊

現在，我們有了這麼棒的資料結構，搭配一個權重由大到小排序的$set$維護目前在圖上的邊
要實現這些操作，有甚麼困難的嗎？

時間複雜度：$O(M\log(N+M))$ ($link-cut\ tree$上總共$N+M$個點)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
unsigned int Rand()
{
    static unsigned int seed=20160217;
    seed*=0xdefaced,seed+=153151;
    return seed+=seed>>20;
}
struct Node
{
    Node *ch[2],*parent,*max_node;
    const int id,v;
    int w,sz;
    bool flipped;
    Node(const int _id,const int _v,const int _w):ch{NULL,NULL},parent(),max_node(this),id(_id),v(_v),w(_w),sz(_w),flipped(false){}
    void Flip()
    {
        flipped^=true;
        swap(ch[0],ch[1]);
    }
    void PutDown()
    {
        if(flipped)
        {
            for(int d=0;d<2;d++)if(ch[d])ch[d]->Flip();
            flipped^=true;
        }
    }
};
int Sz(Node *o){return o?o->sz:0;}
Node *MaxNode(Node *o){return o?o->max_node:NULL;}
Node *Max(Node *a,Node *b)
{
    if(!a||!b)return a?a:b;
    return (a->v)>(b->v)?a:b;
}
void Maintain(Node *o)
{
    assert(!o->flipped);
    o->sz=Sz(o->ch[0])+(o->w)+Sz(o->ch[1]);
    o->max_node=Max(o,Max(MaxNode(o->ch[0]),MaxNode(o->ch[1])));
}
Node* &GetMe(Node *o)
{
    static Node *nill;
    if(o->parent)
    {
        for(int d=0;d<2;d++)if(o->parent->ch[d]==o)return o->parent->ch[d];
    }
    return nill=NULL;
}
void Rotate(Node *o,const int cu)
{
    Node *u=o;o=o->ch[cu];
    assert(o->parent==u);
    GetMe(u)=o;
    o->parent=u->parent;
    u->PutDown(),o->PutDown();
    u->ch[cu]=o->ch[cu^1];
    if(o->ch[cu^1])o->ch[cu^1]->parent=u;
    o->ch[cu^1]=u;
    u->parent=o;
    Maintain(u),Maintain(o);
}
void Balance(Node *o)
{
    if(!o)return;
    if(Sz(o->ch[0])-Sz(o->ch[1])>1)Rotate(o,0);
    else if(Sz(o->ch[1])-Sz(o->ch[0])>1)Rotate(o,1);
}
void PutDownParents(Node *o)
{
    if(GetMe(o))PutDownParents(o->parent);
    o->PutDown();
}
void RotateUp(Node *o)
{
    Node *p=o->parent;
    for(int d=0;d<2;d++)if(p->ch[d]==o)
    {
        Rotate(p,d);
        Balance(o->ch[0]),Balance(o->ch[1]);//懶的分case直接讓它自動平衡 
        return;
    }
    assert(0);
}
void MaintainParents(Node *o)
{
    Maintain(o);
    if(GetMe(o))MaintainParents(o->parent);
}
Node *Splay(Node *o)
{
    PutDownParents(o);
    MaintainParents(o);
    while(GetMe(o))RotateUp(o);
    return o;
}
Node *Access(Node *o)
{
    Node *right;
    for(right=NULL;o;o=o->parent)
    {
        Splay(o);
        o->w-=Sz(right);
        o->w+=Sz(o->ch[1]);
        o->ch[1]=right;
        Maintain(right=o);
    }
    return right;
}
void SetRoot(Node *o){Access(o)->Flip();}
int ODD_CNT;
bool IsConnected(Node *a,Node *b)
{
    Access(a),Splay(a);
    Access(b),Splay(b);
    return a->parent;
}
void Link(Node *a,Node *b)
{
//    printf("Link %d %d\n",a->id,b->id);
    assert(!IsConnected(a,b));
    const int asz=Access(a)->sz,bsz=Access(b)->sz;
    ODD_CNT-=(asz&1)+(bsz&1);
    SetRoot(a);
    Splay(a)->parent=b;
    b->w+=Sz(a);
    const int sz=Access(b)->sz;
    assert(sz==asz+bsz);
    ODD_CNT+=(sz&1);
}
void Cut(Node *a,Node *b)
{
//    printf("Cut %d %d\n",a->id,b->id);
    assert(IsConnected(a,b));
    const int sz=Access(a)->sz;
    ODD_CNT-=(sz&1);
    SetRoot(a);
    Access(b);
    Splay(b);
    assert(b->ch[0]==a);
    b->ch[0]->parent=NULL;
    b->ch[0]=NULL;
    MaintainParents(b);
    const int asz=Access(a)->sz,bsz=Access(b)->sz;
    assert(sz==asz+bsz);
    ODD_CNT+=(asz&1)+(bsz&1);
}
Node *S[100000],*ES[300000];
struct Edge
{
    int a,b,l;
}EDGE[300000];
struct CmpEdgeIdx{bool operator()(const int a,const int b)const
{
    if((ES[a]->v)!=(ES[b]->v))return (ES[a]->v)>(ES[b]->v);
    return a<b;
}};
set<int,CmpEdgeIdx>EDGE_IN_GRAPH;
Node *PathMax(Node *a,Node *b)
{
    SetRoot(a);
    return Access(b)->max_node;
}
void AddEdge(const int ei)
{
    const Edge &e=EDGE[ei];
//    printf("Add %d (%d,%d,%d)\n",ei,e.a,e.b,e.l);
    Link(S[e.a],ES[ei]);
    Link(S[e.b],ES[ei]);
    EDGE_IN_GRAPH.insert(ei);
}
void DeleteEdge(const int ei)
{
    const Edge &e=EDGE[ei];
//    printf("Delete %d (%d,%d,%d)\n",ei,e.a,e.b,e.l);
    Cut(S[e.a],ES[ei]);
    Cut(S[e.b],ES[ei]);
    auto it=EDGE_IN_GRAPH.find(ei);
    assert(it!=EDGE_IN_GRAPH.end());
    EDGE_IN_GRAPH.erase(it);
}
void NewEdge(const int ei)
{
    const Edge &e=EDGE[ei];
    if(IsConnected(S[e.a],S[e.b]))
    {
        Node *max_node=PathMax(S[e.a],S[e.b]);
//        printf("%d %d\n",max_node->id,max_node->v);
        assert((max_node->id)>=0);
        if((max_node->v)<=e.l)return;
        DeleteEdge(max_node->id);
    }
    AddEdge(ei);
}
void DeleteEdges()
{
    const int pre_odd_cnt=ODD_CNT;
    while(!EDGE_IN_GRAPH.empty())
    {
        const int ei=*EDGE_IN_GRAPH.begin();
        DeleteEdge(ei);
        assert(ODD_CNT>=pre_odd_cnt);
        if(ODD_CNT>pre_odd_cnt){AddEdge(ei);assert(ODD_CNT==pre_odd_cnt);break;}
    }
}
int N,M;
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)S[i]=new Node(-i-1,-1,1);
        ODD_CNT=N;
        EDGE_IN_GRAPH.clear();
        for(int i=0;i<M;i++)
        {
            int &a=EDGE[i].a,&b=EDGE[i].b,&l=EDGE[i].l;
            scanf("%d%d%d",&a,&b,&l),a--,b--;
            ES[i]=new Node(i,l,0);
            NewEdge(i);
            if(ODD_CNT==0)DeleteEdges();
            assert(ODD_CNT>=0);
            if(ODD_CNT==0)printf("%d\n",EDGE[*EDGE_IN_GRAPH.begin()].l);
            else puts("-1");
        }
    }
    return 0;
}