2019.2.14 t3 车辆销售

news/2024/7/4 8:25:06

用算法求最大生成树，在并查集合并时，把原本的一个根连向另一个根改成两个根都连向一个新建的节点，并把当前正在处理的边的权值赋给这个新节点做点权。这样形成的结构会是一棵树。一个点的答案大致上是树的根到自己的路径上，相邻两个节点的子树叶节点数的平方和。需要注意的是父子两个节点权值相同的情况，这个部分需要特殊处理。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <cctype>
 7 using namespace std;
 8 
 9 #define LL long long
10 #define res register int
11 inline int read()
12 {
13     int x(0),f(1); char ch;
14     while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
15     while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
16     return f*x;
17 }
18 int n,m;
19 const int N=500000+5;
20 int head[N],nxt[N<<1],ver[N<<1],tot;
21 struct E{
22     int u,v,w;
23 }e[N];
24 int vis[N],fa[N];
25 LL w[N],size[N],val[N];
26 inline bool cmp(E a,E b) {return a.w>b.w;}
27 inline void add(int x,int y) {
28     ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot;
29     ver[++tot]=x; nxt[tot]=head[y]; head[y]=tot;
30 }    
31 
32 inline int get(int x) {
33     if(x==fa[x]) return x; return fa[x]=get(fa[x]);
34 }
35 
36 int cnt(0);
37 inline void Kruskal()
38 {
39     cnt=n;
40     sort(e+1,e+m+1,cmp);
41     for(res i=1 ; i<=n ; i++) fa[i]=i;
42     for(res i=1 ; i<=m ; i++)
43     {
44         int x=get(e[i].u),y=get(e[i].v),z=e[i].w;
45         if(x==y) continue;
46         val[++cnt]=z;
47         fa[cnt]=fa[x]=fa[y]=cnt;
48         add(x,cnt); add(y,cnt);
49         if(cnt==2*n-1) break;
50     }
51 }
52 
53 inline void dfs(int x,int f)
54 {
55     vis[x]=1;
56     for(res i(head[x]) ; i ; i=nxt[i])
57     {
58         int y=ver[i]; if(f==y) continue;
59         dfs(y,x); size[x]+=size[y];
60     }
61 }
62 
63 inline void dp(int x,int f)
64 {
65     for(res i(head[x]) ; i ; i=nxt[i])
66     {
67         int y=ver[i]; if(f==y) continue;
68         if(val[x]==val[y]) size[y]=size[x];
69         w[y]=w[x]+(size[x]-size[y])*(size[x]-size[y]); 
70         dp(y,x);
71     }
72 }
73 
74 inline void work()
75 {
76     for(res i=1 ; i<=n ; i++) size[i]=1;
77     for(res i=1 ; i<=cnt ; i++)
78     {
79         if(vis[i]) continue;
80         int x=get(i);
81         dfs(x,0); 
82         dp(x,0);
83     }
84 }
85 
86 int main()
87 {
88     freopen("car.in","r",stdin);
89     freopen("car.out","w",stdout);
90     n=read(); m=read()-1;
91     for(res i=1 ; i<=m ; i++) {
92         e[i].u=read(); e[i].v=read(); e[i].w=read();
93     }
94     Kruskal();
95     work();
96     for(res i=1 ; i<=n ; i++) cout<<w[i]<<" ";//printf("%d ",w[i]);
97     puts("");
98     return 0;
99 }