Early's Blog

Hello, World!

0%

「FJOI2019」树形交通网络

发表于 分类于
本文字数： 3.4k

题目链接

题意

对于一棵树，你可以进行如下操作：选择两条边 (u1,v1),(u2,v2)(u_1,v_1),(u_2,v_2)，将其修改成 (u1,v2),(u2,v1)(u_1,v_2),(u_2,v_1)。

给定一棵树，支持加点 / 删点（保证仍为一棵树），求这棵树经过至多一次操作后的最大直径。

思路

先抛开加点 / 删点不谈，给定一棵树，至多一次操作后它的最大直径是什么呢？

显然，最大直径至少是它原来的直径。

看看下面这幅图：

“三叉戟”

我们可以选择对 (1,6),(4,5)(1,6),(4,5) 进行操作，操作后的直径为 (1,3),(1,5),(1,8)(1,3),(1,5),(1,8) 这三条边长度之和 −1-1。

而选择不操作时只有一种可能：树退化成一条链。

所以，我们只要维护像 (3,5,8)(3,5,8) 这样的三元组，每次加点的时候判断一下能否更新得更长即可。

但是题目还要求删点啊！

可以用线段树分治解决。

我们在时间轴上建立线段树，将每个点存在的时间区间打上标记，在访问到一个区间时用这个区间的标记点更新三元组。

时间复杂度 O(nlog⁡2n)O(n\log^2n)。

实现

预处理出点对的 LCA 和距离。（如果你能 O(1)O(1) 求出 LCA 的话你可以做到 O(nlog⁡n)O(n\log n)）

三元组的更新繁而不难，只要一个个枚举能否替换 u/v/wu/v/w 即可。

注意特判链的情况（即 w=0w=0）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
const int N=2e5,S=N<<2;
int n,m=1,fro[N+1],to[N+1],fa[N+1],son[N+1],dep[N+1],top[N+1],siz[N+1];
vector<int>v[S+1];
int read()
{
    int res=0;
    char c=getchar();
    while(!isdigit(c)) {
        c=getchar();
    }
    while(isdigit(c)) {
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res;
}
void dfs()
{
    for(int u,v=m;u=fa[v],v!=1;--v) {
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) {
            son[u]=v;
        }
    }
    top[1]=1;
    for(int u,v=2;u=fa[v],v<=m;++v) {
        top[v]=son[u]==v?top[u]:v;
    }
    return;
}
int lca(int u,int v)
{
    while(top[u]!=top[v]) {
        if(dep[top[u]]>dep[top[v]]) {
            u=fa[top[u]];
        } else {
            v=fa[top[v]];
        }
    }
    return dep[u]<=dep[v]?u:v;
}
inline int dis(int u,int v)
{
    return dep[u]+dep[v]-(dep[lca(u,v)]<<1);
}
void change(int num,int l,int r,int fro,int to,int val)
{
    if((fro<=l)&&(to>=r)) {
        v[num].push_back(val);
        return;
    }
    int mid=l+r>>1;
    if(fro<=mid) {
        change(num<<1,l,mid,fro,to,val);
    }
    if(to>mid) {
        change(num<<1|1,mid+1,r,fro,to,val);
    }
    return;
}
inline bool linked(int u,int v)
{
    return (fa[v]==u)||(fa[u]==v);
}
struct triple {
    int u,v,w,uv,uw,vw;
    void update(int x)
    {
        if(w) {
            int ux=dis(u,x),vx=dis(v,x),wx=dis(w,x);
            if(ux+vx>uw+vw) {
                w=x,uw=ux,vw=vx;
            } else {
                if(ux+wx>uv+vw) {
                    v=x,uv=ux,vw=wx;
                } else {
                    if(vx+wx>uv+uw) {
                        u=x,uv=vx,uw=wx;
                    }
                }
            }
        } else {
            if(linked(u,x)) {
                u=x,++uv;
            } else {
                if(linked(v,x)) {
                    v=x,++uv;
                } else {
                    w=x;
                    uw=dis(u,x),vw=dis(v,w);
                }
            }
        }
        return;
    }
    inline int maxlen()
    {
        return w?((uv+uw+vw)>>1)-1:uv;
    }
};
void solve(int num,int l,int r,triple tri)
{
    for(auto i:v[num]) {
        tri.update(i);
    }
    if(l==r) {
        printf("%d\n",tri.maxlen());
        return;
    }
    int mid=l+r>>1;
    solve(num<<1,l,mid,tri),solve(num<<1|1,mid+1,r,tri);
    return;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i) {
        if(read()==1) {
            fa[++m]=read();
            fro[m]=i,to[m]=n;
            dep[m]=dep[fa[m]]+1,siz[m]=1;
        } else {
            to[read()]=i-1;
        }
    }
    dfs();
    for(int i=2;i<=m;++i) {
        change(1,1,n,fro[i],to[i],i);
    }
    solve(1,1,n,triple{1,1,0,0,0,0});
    return 0;
}