[other] Div

https://www.luogu.org/problemnew/show/U16765

解法一

随机输出一组合法解。

复杂度 O(1)

预计得分 10~???

解法二

看完题目基本能想到大力贪心，通过树上差分统计经过每一条边的查询次数，贪心取访问次数最多的到儿子的边作为重链。

复杂度 O(nlogn)

预计得分 60~70

解法三

为什么解法二不能拿到满分呢？

注意到以下数据：

5 3 1 2 2 4 2 5 2 3 1 5 3 4 4 3 标准答案为

2 5 0 0 0 次数为5。

而解法二的答案为

2 3（或4）

0 0 0 次数为6

它是一个十字架型，2为中心，3，4，5均为2的儿子，注意到3~4的查询如果使用重链对答案是没有贡献的，或者说如果一个查询中，两点的LCA如果为某个点的父亲，那么它到该儿子之间的边是不是重链对答案没有影响，在差分的时候这样实现：

    if(g[u][0]!=r)

    {

        tree[u].cnt++;

        tree[r].cnt--;

    }

    if(g[v][0]!=r)

    {

        tree[v].cnt++;

        tree[r].cnt--;

    }

其中g[u][0]为倍增数组，即u的父亲节点，r是u和v的LCA，tree[].cnt是差分的记录变量。复杂度 O(nlogn)

预计得分 100

解法四

模拟退火等随机化算法乱搞，我没试过，但是似乎可能可以得到很好的结果。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

#define gc getchar()

#define lson jd << 1

#define rson jd << 1 | 1

#define important T[jd].w = T[lson].w + T[rson].w

struct Node_1{

    int siz, son, fa, deep, tree, toop;

}P[N];

struct Node_2{

    int v, nxt;

}G[N << ];

struct Node_3{

    int l, r, f, w;

}T[N << ];

int n, Ti, now = , head[N], tim, bef[N], data[N];

inline int read(){

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

inline void add(int u, int v){

    G[now].v = v;

    G[now].nxt = head[u];

    head[u] = now ++;

}

void dfs_find_son(int u, int fa, int dep){

    P[u].fa = fa;

    P[u].deep = dep;

    P[u].siz = ;

    for(int i = head[u]; ~ i; i = G[i].nxt){

        int v = G[i].v;

        if(v != fa) {

            dfs_find_son(v, u, dep + );

            P[u].siz += P[v].siz;

            if(P[v].siz > P[P[u].son].siz) P[u].son = v;

        }

    }

}

void dfs_to_un(int u, int tp){

    P[u].toop = tp;

    P[u].tree = ++ tim;

    bef[tim] = u;

    if(!P[u].son) return ;

    dfs_to_un(P[u].son, tp);

    for(int i = head[u]; ~ i; i = G[i].nxt){

        int v = G[i].v;

        if(v != P[u].son && v != P[u].fa) dfs_to_un(v, v);

    }

}

void down(int jd){

    int F = T[jd].f;

    T[lson].w += (T[lson].r - T[lson].l + ) * F;

    T[rson].w += (T[rson].r - T[rson].l + ) * F;

    T[lson].f += F;

    T[rson].f += F;

    T[jd].f = ;

}

void Sec_G(int l, int r, int jd, int x, int y){

    if(x <= l && r <= y){

        int yj = (r - l) + ;

        T[jd].w += yj;

        T[jd].f ++;

        return ;

    }

    if(T[jd].f) down(jd);

    int mid = (l + r) >> ;

    if(x <= mid) Sec_G(l, mid, lson, x, y);

    if(y > mid) Sec_G(mid + , r, rson, x, y);

    important;

}

inline void Sec_G_imp(int x, int y){

    int tp1 = P[x].toop, tp2 = P[y].toop;

    while(tp1 != tp2){

        if(P[tp1].deep < P[tp2].deep) swap(x, y), swap(tp1, tp2);

        Sec_G(, n, , P[tp1].tree, P[x].tree);

        x = P[tp1].fa;

        tp1 = P[x].toop;

    }

    if(P[x].deep < P[y].deep) Sec_G(, n, , P[x].tree, P[y].tree);

    else Sec_G(, n, , P[y].tree, P[x].tree);

    return ;

}

void Ask_ans(int l, int r, int jd){

    if(l == r) {

        data[bef[l]] = T[jd].w;

        return ;

    }

    if(T[jd].f) down(jd);

    int mid = (l + r) >> ;

    Ask_ans(l, mid, lson);

    Ask_ans(mid + , r, rson);

}

void debug(){

    for(int i = ; i <= n; i ++) cout << data[i] << endl;

    exit();

}

void build_tree(int l, int r, int jd){

    T[jd].l = l; T[jd].r = r;

    if(l == r) return ;

    int mid = (l + r) >> ;

    build_tree(l, mid, lson);

    build_tree(mid + , r, rson);

}

int main()

{

    n = read(); Ti = read();

    for(int i = ; i <= n; i ++) head[i] = -;

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

        int u = read(), v = read();

        add(u, v); add(v, u);

    }

    dfs_find_son(, , );

    dfs_to_un(, );

    build_tree(, n, );

    while(Ti --){

        int x = read(), y = read();

        Sec_G_imp(x, y);

    }

    Ask_ans(, n, );

    //debug();

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

        int answer = -, whoo = ;

        for(int j = head[i]; ~ j; j = G[j].nxt){

            int v = G[j].v;

            if(v == P[v].fa || P[v].tree < P[i].tree) continue ;

            if(data[v] > answer){

                answer = data[v];

                whoo = v;

            }

        }

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

    }

    return ;

}

/*

14 7

1 4

4 10

4 9

4 8

9 13

13 14

3 1

7 3

2 1

2 6

6 12

11 6

5 2

11 3

7 8

2 8

11 1

8 14

5 7

9 14

*/

巴特西

[other] Div

解法一

解法二

解法三

解法四

最新文章

热门文章