HDU6251 Inkopolis

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

typedef struct node{
    int u,v,key;
}node;
node ed[MAXN];
int f[MAXN][21],a[MAXN],num[MAXN],dep[MAXN];
multiset<int>s[MAXN],ss;
multiset<int>::iterator ite,ip;
void dfs(int x,int pre,int deep){
    f[x][0]=pre;dep[x]=deep+1;
    link(x){
        if(j->t!=pre){
            a[j->t]=j->v;
            ite=s[j->t].lower_bound(j->v);
            if(ite==s[j->t].end()||(*ite)!=j->v)num[j->t]++;
            s[j->t].insert(j->v);
            ite=s[x].lower_bound(j->v);
            if(ite==s[x].end()||(*ite)!=j->v)num[x]++;
            s[x].insert(j->v);
            dfs(j->t,x,deep+1);
        }
    }
}
void dfs1(int x){
    for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
    link(x){
        if(j->t!=f[x][0])dfs1(j->t);
    }
}
int Lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int tmp=dep[u]-dep[v];
    for(int i=0;i<=20;i++)if(tmp&(1<<i))u=f[u][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--){
        if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    }
    return f[u][0];
}
bool vis[MAXN];
int fa[MAXN];
int find1(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find1(fa[x]);
}
void debug(int x){
    for(ite=s[x].begin();ite!=s[x].end();ite++)cout<<(*ite)<<" ";
        cout<<endl;
}
int main(){
    int _=read();int ca=0;
    while(_--){
        memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));
        memset(e,0,sizeof(e));memset(h,0,sizeof(h));o=e;
        int n,m;n=read();m=read();ss.clear();
        inc(i,1,n)ed[i].u=read(),ed[i].v=read(),ed[i].key=read(),fa[i]=i,s[i].clear();
        inc(i,1,n){
            int t1=find1(ed[i].u);int t2=find1(ed[i].v);
            if(t1==t2){swap(ed[i],ed[n]);break;}
            fa[t1]=t2;
        }
        inc(i,1,n-1)add(ed[i].u,ed[i].v,ed[i].key),add(ed[i].v,ed[i].u,ed[i].key);
        dfs(1,0,0);dfs1(1);ll ans=0;
        inc(i,1,n)ans+=num[i];
        //cout<<ans<<endl;
        ans-=(n-1);
        int lca=Lca(ed[n].u,ed[n].v);
        int u=ed[n].u;int v=ed[n].v;int key;
        while(u!=lca){ss.insert(a[u]);vis[u]=1;u=f[u][0];}
        while(v!=lca){ss.insert(a[v]);vis[v]=1;v=f[v][0];}
        printf("Case #%d:
",++ca);
        while(m--){
            u=read();v=read();key=read();
            if(min(u,v)==min(ed[n].u,ed[n].v)&&max(v,u)==max(ed[n].v,ed[n].u))ed[n].key=key;
            else{
                int t1;bool flag=0;
                if(dep[u]>dep[v])t1=a[u],flag=vis[u],a[u]=key;else t1=a[v],flag=vis[v],a[v]=key;
                //cout<<flag<<"==="<<u<<" "<<v<<endl;
                if(flag){
                    ite=ss.lower_bound(t1);ss.erase(ite);
                    ss.insert(key);
                }
                //cout<<u<<" "<<t1<<endl;
                //debug(u);
                ite=s[u].lower_bound(t1);s[u].erase(ite);
                ite=s[u].lower_bound(t1);
                //cout<<u<<"===="<<v<<" "<<t1<<endl;
                //cout<<ans<<"::::"<<endl;
                if(ite==s[u].end()||(*ite)!=t1)ans--;
                ite=s[u].lower_bound(key);
                if(ite==s[u].end()||(*ite)!=key)ans++;
                s[u].insert(key);
                ite=s[v].lower_bound(t1);s[v].erase(ite);
                ite=s[v].lower_bound(t1);
                if(ite==s[v].end()||(*ite)!=t1)ans--;
                ite=s[v].lower_bound(key);
                if(ite==s[v].end()||(*ite)!=key)ans++;              
                s[v].insert(key);
                //cout<<ans<<"==="<<endl;
            }
            int tt=ed[n].key;
            ite=ss.begin();ip=ss.end();ip--;
            ll sum=ans;
            //cout<<(*ite)<<" "<<(*ip)<<" "<<tt<<endl;
            if((*ite)==tt&&(*ip)==tt)printf("%lld
",sum);
            else{
                bool flag1=0,flag2=0;
                ite=s[ed[n].u].lower_bound(tt);
                if(ite==s[ed[n].u].end()||(*ite)!=tt)flag1=0;
                else flag1=1;
                ite=s[ed[n].v].lower_bound(tt);
                if(ite==s[ed[n].v].end()||(*ite)!=tt)flag2=0;
                else flag2=1;
                if(flag1&&flag2)sum--;
                else if(!flag1&&!flag2)sum++;
                printf("%lld
",sum);       
            }
        }
    }
    return 0;
}