「题解」「国家集训队」聪明可可

题目链接:Luogu P2634/BZOJ 2152

题解

解法 A(点分治)

思路

题目要求统计树上路径信息,想到点分治。

对于一个节点,设 $ \text{dis} _ {i} $ 为其他节点到这个节点的距离对 $ 3 $ 取模的结果。

那么可以证明,一条经过该节点的合法路径 $ (i, j) $,满足:

$$ \text{dis} _ {i} + \text{dis} _ {j} \equiv 0 ( \bmod 3 ) $$

因此对每个节点求出其子树内的 $ \text{dis} $,经过该点的路径数即为

$$ \sum [ \text{dis} _ {i} = 1 ] \times \sum [ \text{dis} _ {i} = 2 ] + ( \sum [ \text{dis} _ {i} = 0 ] ) ^ {2} $$

然后套用点分治模板即可。

代码

下面是洛谷大神@Orion545的代码,算法的渐进时间复杂度为 $ \Theta ( n \log _ {2} n ) $。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
void _swap(int &x,int &y){x^=y;y^=x;x^=y;}
int _max(int x,int y){return (x>y)?x:y;}
inline int read(){
    int re=0,flag=1;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
int n,cnt,ans,dis[20010],first[20010],tmp[5],root,siz[20010],son[20010],sum;
bool vis[20010];
struct edge{
    int to,next,w;
}a[40010];
inline void add(int u,int v,int w){
    a[++cnt]=(edge){v,first[u],w};first[u]=cnt;
    a[++cnt]=(edge){u,first[v],w};first[v]=cnt;
}
int gcd(int x,int y){return (y?gcd(y,x%y):x);};
void getroot(int u,int f){
    int i,v;
    siz[u]=1;son[u]=0;
    for(i=first[u];~i;i=a[i].next){
        v=a[i].to;
        if(v==f||vis[v]) continue;
        getroot(v,u);
        siz[u]+=siz[v];
        son[u]=_max(son[u],siz[v]);
    }
    son[u]=_max(son[u],sum-siz[u]);
    if(son[u]<son[root]) root=u;
}
void gettmp(int u,int f){
    int i,v;
    tmp[dis[u]]++;
    for(i=first[u];~i;i=a[i].next){
        v=a[i].to;
        if(v==f||vis[v]) continue;
        dis[v]=(dis[u]+a[i].w)%3;
        gettmp(v,u);
    }
}
int calc(int u,int d){  dis[u]=d%3;tmp[0]=tmp[1]=tmp[2]=0;
    gettmp(u,0);
    return tmp[1]*tmp[2]*2+tmp[0]*tmp[0];
}
void dfs(int u){
    int i,v;
    vis[u]=1;ans+=calc(u,0);
    for(i=first[u];~i;i=a[i].next){
        v=a[i].to;
        if(vis[v]) continue;
        ans-=calc(v,a[i].w);
        sum=siz[v];root=0;
        getroot(v,u);
        dfs(root);
    }
}
int main(){
    memset(first,-1,sizeof(first));
    int i,t1,t2,t3;
    n=read();
    for(i=1;i<n;i++){
        t1=read();t2=read();t3=read();
        add(t1,t2,t3);
    }
    sum=n;son[0]=n;
    getroot(1,0);
    dfs(1);
    int div=gcd(n*n,ans); printf("%d/%d",ans/div,n*n/div);
}

解法 B(树形 DP )

思路

与上篇题解相同。

代码

算法的渐进时间复杂度为 $ \Theta ( n ) $。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=20000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n;
int cnt,head[MAXN],to[MAXN<<1],w[MAXN<<1],Next[MAXN<<1];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

inline void Read(void){
    n=read();
    for(reg int i=1;i<n;++i){
        static int x,y,w;
        x=read(),y=read(),w=read();
        Add_Edge(x,y,w);
        Add_Edge(y,x,w);
    }
    return;
}

int ans;
int f[MAXN][3];

inline void DFS(reg int ID,reg int father){
    f[ID][0]=1;
    for(reg int i=head[ID];i;i=Next[i]){
        if(to[i]!=father){
            DFS(to[i],ID);
            for(reg int j=0;j<3;++j)
                ans+=(f[ID][j]*f[to[i]][((-j-w[i])%3+3)%3])<<1;
            for(reg int j=0;j<3;++j)
                f[ID][(j+w[i])%3]+=f[to[i]][j];
        }
    }
    return;
}

inline int gcd(reg int a,reg int b){
    return b==0?a:gcd(b,a%b);
}

inline void Work(void){
    DFS(1,0);
    reg int g=gcd(ans+n,n*n);
    printf("%d/%d\n",(ans+n)/g,n*n/g);
    return;
}