Codeforces Round #425 (Div. 2)

题目链接：http://codeforces.com/contest/832/problem/D

题意：给定一棵n个点的树，然后给你q个询问，每个询问为三元组(a,b,c),问你从这三个点中选取一个作为终点，一个作为Misha的起点，一个作为Grisha的起点。然后每天早上Misha从起点到终点所经过的点都是标记为1，傍晚Grisha从起点到终点所经过的点中带有标记的点的数目最多是多少？

思路：对于每个询问，我们枚举终点(共3种情况)，其余两个点作为一个作为M的起点一个作为G的起点，然后问题就是M的起点到终点这条路径的点赋值1，统计G的起点到终点这条路径的1的个数，然后3种情况取个最大值即可。然后就是经典的树链剖分题目，树剖之后就是区间覆盖+区间查询问题了。起初用的是线段树，然后终测TLE掉了（可能我写的线段树不够优美，被卡常了），后来换成树状数组来维护区间覆盖，区间查询就AC掉了。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<cmath>

using namespace std;

typedef long long int LL;

const int MAXN = 1e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int fa[MAXN],top[MAXN],deep[MAXN],num[MAXN],p[MAXN],fp[MAXN],son[MAXN];

int pos,cp[MAXN],n,q;

LL bit0[MAXN],bit1[MAXN];

vector<int>edge[MAXN];

void init(){

    pos = ;

    memset(bit0,,sizeof(bit0));

    memset(bit1,,sizeof(bit1));

    memset(son, -, sizeof(son));

}

void dfs1(int u, int pre, int d){

    deep[u] = d; fa[u] = pre; num[u] = ;

    for (int i = ; i < edge[u].size(); i++){

        int v = edge[u][i];

        if (v != pre){

            dfs1(v, u, d + );

            num[u] += num[v];

            if (son[u] == - || num[v] > num[son[u]]

                ){

                son[u] = v;

            }

        }

    }

}

void dfs2(int u, int sp){

    top[u] = sp;  p[u] = pos++; fp[p[u]] = u;

    if (son[u] == -){

        return;

    }

    dfs2(son[u], sp);

    for (int i = ; i < edge[u].size(); i++){

        int v = edge[u][i];

        if (v != fa[u] && v != son[u]){

            dfs2(v, v);

        }

    }

}

//BIT

void Add(LL *b,int i,LL val){

    while (i<=n){

        b[i]+=val; i+=i&-i;

    }

}

LL Sum(LL *b,int i){

    LL s=;

    while (i>){

        s+=b[i]; i-=i&-i;

    }

    return s;

}

void Modify(int l,int r,int val){ //区间[l,r] + val

    //printf("M:%d %d %d\n",l,r,val);

    Add(bit0,l,-val*(l-));

    Add(bit1,l,val);

    Add(bit0,r+,val*r);

    Add(bit1,r+,-val);

}

int Query(int l,int r){ //区间[l,r] 1 的个数

    //printf("Q:%d %d\n",l,r);

    LL res=;

    res+=Sum(bit0,r)+1LL*Sum(bit1,r)*r;

    res-=Sum(bit0,l-)+1LL*Sum(bit1,l-)*(l-);

    return res;

}

void solveC(int u, int v,int val){ //修改链

    int f1 = top[u], f2 = top[v];

    while (f1!=f2){

        if (deep[f1] < deep[f2]){

            swap(f1, f2); swap(u, v);

        }

        Modify(p[f1], p[u], val);

        u = fa[f1];

        f1 = top[u];

    }

    if (deep[u] > deep[v]){

        swap(u, v);

    }

    Modify(p[u], p[v], val);

}

int solveQ(int u, int v){ //查询链

    int f1 = top[u], f2 = top[v];

    int tmp = ;

    while (f1 != f2){

        if (deep[f1] < deep[f2]){

            swap(f1, f2); swap(u, v);

        }

        tmp+=Query(p[f1], p[u]);

        u = fa[f1]; f1 = top[u];

    }

    if (deep[u] > deep[v]){

        swap(u, v);

    }

    tmp+=Query(p[u], p[v]);

    return tmp;

}

int solve(int s, int t, int f){

    solveC(s, f, );

    int tmp = solveQ(t, f);

    solveC(s, f, -);

    return tmp;

}

int main(){

#ifdef kirito

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    while (~scanf("%d%d",&n,&q)){

        init();

        for (int i = ; i <= n; i++){

            edge[i].clear();

        }

        for (int i = ; i <= n; i++){

            scanf("%d", &cp[i]);

            edge[cp[i]].push_back(i);

            edge[i].push_back(cp[i]);

        }

        dfs1(, , );

        dfs2(, );

        for (int i = ; i <= q; i++){

            int a, b, c,res=;

            scanf("%d%d%d", &a, &b, &c);

            res = max(res, solve(a, b, c));

            res = max(res, solve(a, c, b));

            res = max(res, solve(b, c, a));

            printf("%d\n", res);

        }

    }

    return ;

}

巴特西

Codeforces Round #425 (Div. 2) - D

最新文章

热门文章