刚学oi dsu on tree0分求助
查看原帖
刚学oi dsu on tree0分求助
74863
ShallowDream雨梨楼主2023/8/5 09:56
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define bianli for(int i=head[x];i;i=a[i].next)
#define mod 998244353
#define QWQ cout<<"qwq";
#define me(qw) memset(qw,0,sizeof(qw));
#define meinf(qw) memset(qw,0x3f,sizeof(qw));
using namespace std;
const int maxn=2e5+5;
int num[5],cnt,f[maxn],dis[maxn],head[maxn],tot,dep[maxn],sz[maxn],wson[maxn],dfn[maxn],id[maxn],ans;
struct road {
   int to,next,v;
} a[maxn*2];
void addedge(int x,int y,int z) {
   a[++tot].to=y;
   a[tot].v=z;
   a[tot].next=head[x];
   head[x]=tot;
}

void dfs(int x,int fa) {
   dep[x]=dep[fa]+1;
   f[x]=fa;
   sz[x]=1;
   dfn[x]=++cnt;
   id[cnt]= x;
   for(int i=head[x]; i; i=a[i].next) {
       int to=a[i].to;
       if(to==fa)continue;
       dis[to]=dis[x]+a[i].v;
       dfs(to,x);
       sz[x]+=sz[to];
       if(sz[wson[x]]<sz[to])wson[x]=to;
   }
}
void calc(int x,int lca) {
   int res= dis[lca]*2-dis[x];
   res+=3;
   res%=3;
   ans+=num[ res];
}
void add(int x) {
   //cout<<x;
   num[dis[x]%3]++;
}

void dsu(int x,int fa,int keep) {
   //	cout<<x<<fa<<keep<<endl;
   for(int i=head[x]; i; i=a[i].next) {
       int to=a[i].to;
       if(to==fa||to==wson[x])continue;
       dsu(to,x,0);
   }
   if(wson[x]) dsu(wson[x],x,1);
   for(int i=head[x]; i; i=a[i].next) {
       int to=a[i].to;
       if(to==fa||to==wson[x])continue;
       for(int i=dfn[to]; i< dfn[to]+sz[to]; i++)
           calc(id[i],x);
       for(int i=dfn[to]; i< dfn[to]+sz[to]; i++)
           add(id[i]);
   }

   calc(x,x);
   add(x);
   if(keep==0) me(num);
}
int gcd(int x,int y) {
   if(y==0)return x;
   return gcd(y,x%y);
}
void solve() {
   int n,q,w,e;
   cin>>n;
   for(int i=1; i<n; i++) {
       cin>>q>>w>>e;
       addedge(q,w,e);
       addedge(w,q,e);
   }
   dfs(1,0);
   dsu(1,0,1);
   //for(int i=1;i<=n;i++)cout<<dis[i];
   ans*=2;
   ans+=n;
   int gd=gcd(ans,n*n);
   ans/=gd;
   int p=n*n/gd;
   cout<<ans<<'/'<<p;
}

signed main() {
//	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int t;
   t=1;

   while(t--)solve();
   return 0;
}
2023/8/5 09:56
加载中...