意

不断删去度数为1的点，最后求有奇数个点的联通块的权值之和。

分析

存边的时候，要头尾都存这个边。用dfs或者队列删点，再用并查集或者dfs确定联通块，然后统计联通块的点数，最后累加。

我自己写的超时，然后参考了网上的题解。真郁闷。

代码

并查集

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int N = 1e4 + 10;ll v[N];ll s[N];int n,m,e[N],f[N],cn[N];vector
        
          d[N];int find(int a){    return f[a]==a?a:find(f[a]);}void unite(int a,int b){    a=find(a),b=find(b);    if(a!=b) f[a]=b;}void add(int a,int b){    e[a]++;    e[b]++;    d[a].push_back(b);    d[b].push_back(a);    unite(a,b);}void del(){    queue
         
          q;    for(int i=1; i<=n; i++) if(e[i]==1) q.push(i);    while(!q.empty())    {        int r=q.front();        q.pop();        for(int j=0; j
          
           1) { int a=find(i); s[a]+=v[i]; cn[a]++; } } ll ans=0; for(int i=1; i<=n; i++) { if (f[i]==i && cn[i]&1) { ans+=s[i]; } } printf("%lld\n",ans); } return 0;}
          
         
        
       
      
     

 

dfs确定联通块

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int N = 1e4 + 10;ll v[N];int n,m,e[N],vis[N];ll ct,sum;vector
        
          d[N];void add(int a,int b){    e[a]++;    e[b]++;    d[a].push_back(b);    d[b].push_back(a);}void dfs(int a){    vis[a]=1;    sum+=v[a];    ct++;    for(int i=0; i
         

q; for(int i=1; i<=n; i++) { if(e[i]==1) q.push(i); if(e[i]==0) vis[i]=1; // 别忘了度为0的点 } while(!q.empty()) { int r=q.front(); vis[r]=1; q.pop(); for(int j=0; j