P2634题解

· · 题解

看到没人写详细的点分题解，我来一发

点分是个很神奇的算法，链接里把两道 模板题讲的很清楚，我就不讲了
我把这题统计答案的部分仔细地讲一讲
首先我们可以把所有点到根节点的距离模上3
然后我们将节点按照距离排序

把根节点也看做树中的一个节点，不分开讨论

然后我们令pos1为最后一个到根节点的距离为0的位置
记cnt1[i]为j=1~pos1中tree[j].from==i节点的总数

ans+=cnt1[i]\times(pos-cnt1[i]);

统计完了两端距离和为0的点对，我们还要统计距离和为3的点对
令pos2为最后一个到根节点的距离为1的位置
记cnt2[i]为j=pos1+1~pos2中tree[j].from==i节点的总数
记cnt3[i]为j=pos2+1~sum中tree[j].from==i节点的总数

ans+=cnt3[i]\times(sum-pos2-wxb[i])*2;

上代码


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int NR=2e4+10;
int n,m;
struct edge{
    int to,next,val;
}g[NR<<1];
int fte[NR];
int tot;
int lcy2;
void add(int x,int y,int z){
    g[++tot]=(edge){y,fte[x],z};
    fte[x]=tot;
}
int rt;
int sizee[NR];
int maxp[NR];
bool vis[NR];
int ask[NR];
struct node{
    int dis,from;
    bool operator <(const node &T)const{
        if(dis!=T.dis)return dis<T.dis;
        return from<T.from;
    }
}t[NR];
int ans;
int sum;
void get_root(int id,int fa){
    sizee[id]=1; 
    maxp[id]=0;
    for(int i=fte[id];i;i=g[i].next){
        int x=g[i].to;
        if(x==fa||vis[x])continue;
        get_root(x,id);
        sizee[id]+=sizee[x];
        maxp[id]=max(maxp[id],sizee[x]);
    }
    maxp[id]=max(maxp[id],sum-sizee[id]);
    if(maxp[id]<maxp[rt])rt=id;
}
void init_dist(int id,int fa,int val){
    t[++sum].dis=val;
    for(int i=fte[id];i;i=g[i].next){
        int x=g[i].to;
        if(vis[x]||fa==x)continue;
        init_dist(x,id,val+g[i].val);
    }
}
int lcy;
void init_from(int id,int fath,int k){
    t[++lcy].from=k;
    for(int i=fte[id];i;i=g[i].next){
        int x=g[i].to;
        if(vis[x]||fath==x)continue;
        init_from(x,id,k);
    }
}
int wxb[NR];
int cnt;
int temp[NR];
void process(){
    for(int i=1;i<=sum;i++)t[i].dis%=3;
    sort(t+1,t+1+sum);
    int pos=sum;
    int maxn=0;
    for(int i=1;i<=sum;i++)
        maxn=max(maxn,t[i].dis);
    for(int i=1;i<=sum;i++)
        if(t[i].dis>0){
            pos=i-1;
            break;
        }
    for(int i=0;i<=sum;i++)wxb[i]=0;
    for(int i=1;i<=pos;i++)
        wxb[t[i].from]++;
    for(int i=0;i<=cnt;i++)
        ans+=wxb[i]*(pos-wxb[i]);
    if(maxn<2)return;
    int pos2;
    for(int i=pos+1;i<=sum;i++)
        if(t[i].dis==2){
            pos2=i-1;
            break;
        }
    for(int i=1;i<=sum;i++)wxb[i]=0;
    for(int i=pos2+1;i<=sum;i++)
        wxb[t[i].from]++;
    for(int i=1;i<=sum;i++)temp[i]=0;
    for(int i=pos+1;i<=pos2;i++)
        temp[t[i].from]++;
    for(int i=1;i<=cnt;i++)
        ans+=temp[i]*(sum-pos2-wxb[i])*2;
}
void solve(int id){
    for(int i=1;i<=n;i++)t[i].dis=0;
    maxp[0]=0x3f3f3f3f;
    rt=0;
    get_root(id,0);
    id=rt;
    t[1].dis=0;
    vis[id]=true;
    sum=0;
    init_dist(id,0,0);
    //处理距离
    lcy=1;
    cnt=0;
    for(int i=fte[id];i;i=g[i].next){
        int x=g[i].to;
        if(vis[x])continue;
        init_from(x,id,++cnt);
    }
    process();
    for(int i=fte[id];i;i=g[i].next)
        if(!vis[g[i].to])
            solve(g[i].to);
}
int gcd(int x,int y){
    if(!x||!y)return x+y;
    return gcd(y,x%y);
}
int main(int argc, char const *argv[])
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    solve(1);
    int dcx1=ans+n;
    int dcx2=n*n;
    int num=gcd(dcx1,dcx2);
    dcx1/=num;
    dcx2/=num;
    printf("%d/%d\n",dcx1,dcx2);
}
//代码稍长，且变量名经处理，防抄