【CF1023F】Mobile Phone Network（dsu on tree，MST）

题意：

保证原边以边权单调非减的顺序读入

思路：先把未知边加入，再加入原始边做MST，考虑从大到小，用数据结构维护，每一条原始边相当两个链赋值操作，每一条未知边相当于一个询问，答案即为询问之和

LCT和树剖都能维护

但因为没有强制在线，可以使用并查集维护

考虑做完MST后预处理出深度，父亲，父边权值三个信息

枚举没有用过的原始边，用类似树剖的方法用并查集每次将一个操作中所有的点缩成一个，暴力更改边权

若有未赋值过的边则无解

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 #include<bitset>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef unsigned int uint;
 15 typedef unsigned long long ull;
 16 typedef pair<int,int> PII;
 17 typedef vector<int> VI;
 18 #define fi first
 19 #define se second 
 20 #define MP make_pair
 21 #define N      1100000
 22 #define M      51
 23 #define MOD 1000000007
 24 #define eps 1e-8 
 25 #define pi     acos(-1)
 26 #define oo     1e9
 27 
 28 struct arr
 29 {
 30     int x,y,z;
 31 }a[N];
 32 
 33 struct node
 34 {
 35     int x,y;
 36     node(int a,int b)
 37     {
 38         x=a; 
 39         y=b;
 40     }
 41 };
 42 
 43 int f[N],g[N],fa[N],dep[N],b[N];
 44 vector<node>c[N];
 45 
 46 int find(int k)
 47 {
 48     if(fa[k]!=k) fa[k]=find(fa[k]);
 49     return fa[k];
 50 }
 51 
 52 void dfs(int u)
 53 {
 54     dep[u]=dep[f[u]]+1;
 55     for(int i=0;i<=(int)c[u].size()-1;i++)
 56     {
 57         int v=c[u][i].x;
 58         if(v!=f[u])
 59         {
 60             f[v]=u;
 61             g[v]=c[u][i].y;
 62             dfs(v);
 63         }
 64     }
 65 }
 66  
 67 int main()
 68 { 
 69     int n,k,m;
 70     scanf("%d%d%d",&n,&k,&m); 
 71     for(int i=1;i<=n;i++) fa[i]=i;
 72     for(int i=1;i<=k;i++)
 73     {
 74         int x,y;
 75         scanf("%d%d",&x,&y);
 76         c[x].push_back(node(y,0));
 77         c[y].push_back(node(x,0));
 78         fa[find(x)]=find(y);
 79     }
 80     for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
 81     for(int i=1;i<=m;i++)
 82     {
 83         int t1=find(a[i].x);
 84         int t2=find(a[i].y);
 85         if(t1!=t2)
 86         {
 87             fa[t1]=t2;
 88             c[a[i].x].push_back(node(a[i].y,a[i].z));
 89             c[a[i].y].push_back(node(a[i].x,a[i].z));
 90             b[i]=1;
 91         }
 92     }
 93     f[1]=1;
 94     dfs(1);
 95     for(int i=1;i<=n;i++) fa[i]=i;
 96     ll ans=0;
 97     for(int i=1;i<=m;i++)
 98      if(!b[i])
 99      {
100          int x=find(a[i].x),y=find(a[i].y);
101          while(x!=y)
102          {
103              if(dep[x]<dep[y]) swap(x,y);
104              if(!g[x]) 
105              {
106                  ans+=a[i].z;
107                  g[x]=a[i].z;
108              }
109              fa[x]=find(f[x]);
110              x=find(x);
111          }
112     }
113     for(int i=2;i<=n;i++)
114      if(!g[i])
115      {
116          printf("-1
");
117          return 0;
118      }
119     printf("%lld
",ans);
120     return 0;
121 }