A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2152 聪聪可可 点分治
发表于: | 分类: Oi | 评论:0 | 阅读:120

给定一个树,求求多少条简单路径的长度是3的倍数

基本上和poj 1741是一个题目

不懂得树分治的可以看那个
然后不同的是计算答案的方法
但是这个东西比较套路了,显然我们只需要求一个对3取模的深度就行了,然后每次余1余2的乘在一起,余0的自己单独搞出来
但是题中 的要求比较诡异,自己多注意下细节就好了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 20000+5;
const int M = N << 2;
typedef long long LL;
using namespace std;

int head[N];
bool vis[N];

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z); head[y] = cnt;
}

int root,sum;
int F[N],size[N],dis[N];

void DFS1(int x,int fa)
{
    size[x] = 1, F[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa && !vis[edge[i].to])
        {
            DFS1(edge[i].to,x);
            size[x] += size[edge[i].to];
            F[x] = max(F[x],size[edge[i].to]);
        }
    F[x] = max(F[x],sum-size[x]);
    root = F[x] < F[root] ? x : root;
}

int stack[N],top;

void DFS2(int x,int fa)
{
    stack[++top] = dis[x];
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
        {
            dis[edge[i].to] = (dis[x] + edge[i].val)%3;
            DFS2(edge[i].to,x);
        }
}

LL get_ans(int x,int d)
{
    LL tmp[3] = {};
    top = 0,dis[x] = d;DFS2(x,x);
    LL ans = 0;
    for(int i=1;i<=top;++i) tmp[stack[i] %3] ++;
    ans += tmp[0] * (tmp[0]-1)+ tmp[1] * tmp[2] * 2;
    return ans;
}

LL ans = 0;

void solve(int x)
{
    int tmp = get_ans(x,0);
    //cout << x << " " << tmp << endl;
    ans += tmp; vis[x] = 1;
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
        {
            ans -= get_ans(edge[i].to,dis[edge[i].to]);
            sum = size[edge[i].to],root = 0;
            DFS1(edge[i].to,edge[i].to);
            solve(root);
        }
}

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    LL n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(), y = read(), z = read();
        add(x,y,z);
    }
    sum = n, F[root = 0] = 0x7fffffff;
    DFS1(1,1);
    solve(root);
    ans += n;
    printf("%lld/%lld\n",ans/__gcd(n*n,ans),n*n/__gcd(n*n,ans));
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP