首页 > 代码库 > BZOJ3083: 遥远的国度

BZOJ3083: 遥远的国度

2024-07-10 04:10:33   220人阅读

3083: 遥远的国度

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 839  Solved: 192
[Submit][Status]

Description

描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。

问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。

Input

第1行两个整数n m，代表城市个数和操作数。
第2行至第n行，每行两个整数 u v，代表城市u和城市v之间有一条路。
第n+1行，有n个整数，代表所有点的初始防御值。
第n+2行一个整数 id，代表初始的首都为id。
第n+3行至第n+m+2行，首先有一个整数opt，如果opt=1，接下来有一个整数id，代表把首都修改为id；如果opt=2，接下来有三个整数p1 p2 v，代表将p1 p2路径上的所有城市的防御值修改为v；如果opt=3，接下来有一个整数 id，代表询问以城市id为根的子树中的最小防御值。

Output


对于每个opt=3的操作，输出一行代表对应子树的最小点权值。

Sample Input

3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1

Sample Output

1
2
3
4
提示
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。

HINT

Source

zhonghaoxi提供

 

orz钟神的题，这题有个换根操作，但是仔细想想，其实不“影响”dfs序的

树链剖分得到的也是一个合法的dfs序，对于换根操作，默认根节点为1

假设现在的根是root，那么只有在root到1路径上的点答案会受影响，其余的点就是查询子树就完了

至于在root到1路径上的点，发现，换根过后，所查询的区间是（这有点难描述）

上张图吧

查询的点是x

那么除了红色圈的那颗子树以外，其余的点就是我要查询的点，也就是里x最近的属于root到1路径上的点，在dfs序上是连续的一段，那么就查询补集就行

还是挺水的吧，，修改是一段区间，所以给个标记就行

注意root==x情况就是整棵子树

 /*Author:wuhuajun*/#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1using namespace std; typedef long long ll;typedef double dd;const int maxn=200010;const ll INF = (ll)1E14 + 9; int h[maxn], n, m, top[maxn], lca[maxn][21], son[maxn], edge, sz[maxn], dep[maxn];int L[maxn], R[maxn], root, num, x, y, tx, ty, t, opt;ll val, a[maxn]; struct Edge{    int to, ne;} e[maxn * 2]; struct Seg{    ll minn, same;} seg[maxn << 2]; void close(){    exit(0);} void addedge(int x,int y){    e[edge].to = y;    e[edge].ne = h[x];    h[x] = edge++;} void dfs(int k,int from){    sz[k] = 1;    dep[k] = dep[from] + 1;    son[k] = 0;    for (int p=h[k];p!=-1;p=e[p].ne)    {        int to = e[p].to;        if (to == from) continue;        lca[to][0] = k;        for (int i=1;i<=20;i++)            lca[to][i] = lca[lca[to][i-1]][i-1];        dfs(to, k);        sz[k] += sz[to];        if (sz[to] > sz[son[k]]) son[k] = to;    }} void build(int k,int from){    L[k] = ++num;    top[k] = from;    if (son[k]) build(son[k], from);    for (int p=h[k];p!=-1;p=e[p].ne)    {        int to = e[p].to;        if (to != lca[k][0] && to != son[k])            build(to, to);    }    R[k] = num;} int get_lca(int x,int y){    if (dep[x] < dep[y]) swap(x, y);    int depth = dep[x] - dep[y];    for (int i=20;i>=0;i--)        if (depth & (1 << i))            x = lca[x][i];    if (x == y) return x;    for (int i=20;i>=0;i--)    {        if (lca[x][i] != lca[y][i])        {            x = lca[x][i];            y = lca[y][i];        }    }    return lca[x][0];} void pushup(int rt){    seg[rt].minn = min(seg[rt<<1].minn, seg[rt<<1|1].minn);} void same(int rt,ll val){    seg[rt].minn = val;    seg[rt].same = val;} void pushdown(int rt){    if (seg[rt].same)    {        same(rt << 1, seg[rt].same);        same(rt << 1 | 1, seg[rt].same);        seg[rt].same = 0;    }} void change(int L,int R,ll val,int l,int r,int rt){    if (L <= l && r <= R)    {        same(rt, val);        return;    }    int mid = (l + r) >> 1;    pushdown(rt);    if (L <= mid)        change(L,R,val,lson);    if (mid + 1 <= R)        change(L,R,val,rson);    pushup(rt);} ll query(int L,int R,int l,int r,int rt){    if (L > R) return INF;    if (L <= l && r <= R)    {        return seg[rt].minn;    }    int mid = (l + r) >> 1;    pushdown(rt);    ll ans = INF;    if (L <= mid)        ans = min(ans, query(L,R,lson));    if (mid + 1 <= R)        ans = min(ans, query(L,R,rson));    pushup(rt);    return ans;} void cc(){    tx = top[x];    ty = top[y];    while (tx != ty)    {        if (dep[tx] < dep[ty])        {            swap(x, y);            swap(tx, ty);        }        change(L[tx], L[x], val, 1, n, 1);        x = lca[tx][0];        tx = top[x];    }    if (dep[x] < dep[y])        swap(x, y);    change(L[y], L[x], val, 1, n, 1);} void work(){    if (root == x)    {        printf("%lld\n", seg[1].minn);//询问全局的        return;    }    t = get_lca(root, x);    if (t != x) //表示不在它到根的路径上    {        printf("%lld\n", query(L[x], R[x], 1, n, 1));        return;    }    int depth = dep[root] - dep[x] - 1;    int haha = root;    for (int i=20;i>=0;i--)        if (depth & (1 << i))            haha = lca[haha][i];    printf("%lld\n", min(query(1, L[haha] - 1, 1, n, 1), query(R[haha] + 1, n, 1, n, 1)) );} void init(){    scanf("%d %d",&n,&m);    memset(h, -1, sizeof(h));    for (int i=1;i<=n-1;i++)    {        scanf("%d %d",&x, &y);        addedge(x, y);        addedge(y, x);    }    for (int i=1;i<=n;i++)        scanf("%lld",&a[i]);    dfs(1, 0);    build(1, 1);    /*    for (int i=1;i<=n;i++)        printf("i:%d top:%d hash:%d son:%d\n",i, top[i], L[i], son[i]);    close();    */    for (int i=1;i<=n;i++)        change(L[i], L[i], a[i], 1, n, 1);    scanf("%d",&root);    while (m--)    {        scanf("%d",&opt);        if (opt == 1) scanf("%d",&root);        if (opt == 2)        {            scanf("%d %d %lld",&x,&y,&val);            cc();        }        if (opt == 3)        {            scanf("%d",&x);            work();        }    }} int main (){    init();    close();    return 0;}

 


联系
我们