树链剖分

题目链接：http://www.luogu.org/problemnew/show/3384

简介:一道树剖模板题

关于树剖：

步骤一：第一次dfs

求出每个节点的重儿子（最重的儿子）和每个节点的质量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs1(int st)
{
    size[st]=1;
    for(int i=head[st]; i; i=E[i].next)
    {
        int ed=E[i].ed;
        if(fa[st]!=ed)
        {
            dep[ed]=dep[st]+1;
            fa[ed]=st;
            dfs1(ed);
            if(hson[st]==0||size[hson[st]]<size[ed])    hson[st]=ed;
            size[st]+=size[ed];
        }
    }
}

伪代码：

1
2
3
4
5
6
7
8
Func dfs1(st)
    Size[st]=1
    For(every node ed connected to the current node)
        If(is not father of node now)
            Depth[ed]=depth[st]+1
            Father[ed]=st
            Check whether ed is the heaviest
            Size[st]+=size[ed]
步骤二：第二遍搜索：求出每一条重边的祖先，建立题目所给的节点序号和线段树存储序号的映射

在线段树中，存储的是重节点优先的先序遍历，好处有二：

1：以s为根的子树的节点是连续的

2：每一条重边都是连续的

C++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs2(int st,int anc)
{
    top[st]=anc;//求重边祖先
    sid[st]=++tot;//建立映射
    real[tot]=st;//建立映射
    if(hson[st]==0) return;
    dfs2(hson[st],anc);//重儿子优先
    for(int i=head[st]; i; i=E[i].next)
    {
        int ed=E[i].ed;
        if(ed!=fa[st]&&ed!=hson[st])
            dfs2(ed,ed);//其他儿子是轻边
    }
}

伪代码：

1
2
3
4
5
6
7
8
Func dfs2(int st,int ancester)
    Top[st]=ancestor
    Build_connection(st)
    If exist heavy_son
        Dfs2(heavy_son,ancestor)
    For(every node ed connected to the current node)
        If(is not father of node now  AND  is not the heavy_son)
        Dfs2(ed,ed)

步骤三，建立一颗加法线段树 这里的build_tree函数有一点不一样：
1
2
3
4
5
6
7
8
9
10
11
12
void build_tree(int L,int R,int id)
{
    if(L==R)
    {
        T[id].sum=a[real[L]];//一定要考虑题目编号和线段树编号之间的映射！！！
        return;
    }
    int mid=(L+R)/2;
    build_tree(L,mid,id<<1);
    build_tree(mid+1,R,id<<1|1);
    pushup(id);
}

以上是预备工作，以下还有两种修改，两种查询：

子树修改：

由于是先序遍历，以x为根的子节点肯定在线段树区间][ sid[x],sid[i]+size[x]-1 ]内

只有一行代码：

modify(sid[x],sid[x]+size[x]-1，num_to_add);//这是伪代码

子树查询：

只是把修改换成了查询而已

1
Query(sid[x],sid[x]+size[x]-1)
重头戏：链修改 u to v（题目序号）

1：u，v在一条重边上

保持大小关系，之后modify（sid[u],sid[v],num_to_add）

2: u,v不在一条重边上：

那么u和v不停地向上跳，一定会跳到一条重边上

每次选取所在链的所在链头结点较低的那一条链进行统计，统计完了之后在向上加（跳）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void chain_add()
{
    LL u,v,w,tu,tv;
    scanf("%lld%lld%lld",&u,&v,&w);
    tu=top[u],tv=top[v];
    while(tu!=tv)
{
        if(dep[tu]<dep[tv])
            swap(tu,tv),swap(u,v);
        modify(sid[tu],sid[u],w,1,N,1);
        u=fa[tu];
        tu=top[u];
    }
    if(dep[u]<dep[v])   swap(u,v);
    modify(sid[v],sid[u],w,1,N,1);
}

伪代码：

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
Func chain_add(u,v)
    Tu=top[u]    tv=top[v]
    While(not in the same chain => tu!=tv)
        Make u the deepest
        modify(sid[tu],sid[u])
        Jump    =>  u=father[tu] tu=top[u]
Make u the deepest
Modify(sid[v],sid[u])
##### 查询：把线段树修改换成查询
​```c++
void chain_query()
{
    LL u,v,tu,tv,ret=0;
    scanf("%lld%lld",&u,&v);
    tu=top[u],tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv])
        {
            swap(tu,tv);
            swap(u,v);
        }
        ret+=query(sid[tu],sid[u],1,N,1);
        ret%=P;
        u=fa[tu];
        tu=top[u];
    }
    if(dep[u]<dep[v])   swap(u,v);
    ret+=query(sid[v],sid[u],1,N,1);
    printf("%lld\n",ret%P);
}

代码：

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
struct edge
{
    int ed,next;
} E[int(1e6)+10];
int head[100100],Ecnt;
int N,M,R,P;
LL a[100100];
struct node
{
    LL sum,atag;
} T[100100<<3];
LL real[100010],sid[100010],hson[100010],fa[100010],dep[100010],size[100010],top[100010];
LL tot;
// code
void addEdge(int st,int ed)
{
    E[++Ecnt].ed=ed;
    E[Ecnt].next=head[st];
    head[st]=Ecnt;
}
void dfs1(int st)
{
    size[st]=1;
    for(int i=head[st]; i; i=E[i].next)
    {
        int ed=E[i].ed;
        if(fa[st]!=ed)
        {
            dep[ed]=dep[st]+1;
            fa[ed]=st;
            dfs1(ed);
            if(hson[st]==0||size[hson[st]]<size[ed])    hson[st]=ed;
            size[st]+=size[ed];
        }
    }
}
void dfs2(int st,int anc)
{
    //printf("dfs2 st=%d anc=%d\n",st,anc);
    top[st]=anc;
    //printf("top[%d]=%d\n",st,top[st]);
    sid[st]=++tot;
    real[tot]=st;
    if(hson[st]==0) return;
    dfs2(hson[st],anc);
    for(int i=head[st]; i; i=E[i].next)
    {
        int ed=E[i].ed;
        if(ed!=fa[st]&&ed!=hson[st])
            dfs2(ed,ed);
    }
}
/// 线段树
void pushup(int id)
{
    T[id].sum=T[id<<1].sum+T[id<<1|1].sum;
}
void pushdown(int L,int R,int id)
{
    if(T[id].atag)
    {
        if(L!=R)
        {
            T[id<<1].atag+=T[id].atag;
            T[id<<1|1].atag+=T[id].atag;
        }
        T[id].sum+=(R-L+1)*T[id].atag;
        T[id].atag=0;
    }
}
void build_tree(int L,int R,int id)
{
    if(L==R)
    {
        T[id].sum=a[real[L]];
        return;
    }
    int mid=(L+R)/2;
    build_tree(L,mid,id<<1);
    build_tree(mid+1,R,id<<1|1);
    pushup(id);
}
void modify(int B,int E,int x,int L,int R,int id)
{
    if(L>E||R<B)    return;
    pushdown(L,R,id);
    if(L>=B&&R<=E)
    {
        T[id].atag+=x;
        return;
    }
    int mid=(L+R)>>1;
    modify(B,E,x,L,mid,id<<1);
    modify(B,E,x,mid+1,R,id<<1|1);
    pushdown(L,mid,id<<1);
    pushdown(mid+1,R,id<<1|1);
    pushup(id);
}
LL query(int B,int E,int L,int R,int id)
{
    if(L>E||R<B)    return 0ll;
    pushdown(L,R,id);
    if(L>=B&&R<=E)
        return T[id].sum%P;
    int mid=(L+R)>>1;
    return query(B,E,L,mid,id<<1)+query(B,E,mid+1,R,id<<1|1);
}
///end of segment tree
void tree_add()
{
    //cout<<__func__<<endl;
    LL x,v;
    scanf("%lld%lld",&x,&v);
    modify(sid[x],sid[x]+size[x]-1,v,1,N,1);
}
void tree_query()
{
    //cout<<__func__<<endl;
    LL x;
    scanf("%lld",&x);
    printf("%lld\n",query(sid[x],sid[x]+size[x]-1,1,N,1)%P);
}
void chain_add()
{
    //cout<<__func__<<endl;
    LL u,v,w,tu,tv;
    scanf("%lld%lld%lld",&u,&v,&w);
    //cout<<"["<<u<<","<<v<<"]"<<endl;
    tu=top[u],tv=top[v];
    //printf("%lld %lld\n",tu,tv);
    while(tu!=tv)
    {
        //printf("dep[tu]=%lld,dep[tv]=%lld\n",dep[tu],dep[tv]);
        if(dep[tu]<dep[tv])
        {
            swap(tu,tv);
            swap(u,v);
        }
        modify(sid[tu],sid[u],w,1,N,1);
        //printf("modifyed %lld to %lld\n",tu,u);
        u=fa[tu];
        tu=top[u];
    }
    if(dep[u]<dep[v])   swap(u,v);
    modify(sid[v],sid[u],w,1,N,1);
       // printf("modified %lld to %lld\n",v,u);
}
void chain_query()
{
    //printf("\t%lld\n",query(sid[3],sid[3],1,N,1));
    //cout<<__func__<<endl;
    LL u,v,tu,tv,ret=0;
    scanf("%lld%lld",&u,&v);
    tu=top[u],tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv])
        {
            swap(tu,tv);
            swap(u,v);
        }
        LL t=query(sid[tu],sid[u],1,N,1);
        //printf("queryed %lld to %lld      == %lld\n",tu,u,t);
        ret+=query(sid[tu],sid[u],1,N,1);
        ret%=P;
        //cout<<ret<<endl;
        u=fa[tu];
        tu=top[u];
    }
    if(dep[u]<dep[v])   swap(u,v);
    LL t=query(sid[v],sid[u],1,N,1);
        //printf("queryed %lld to %lld      == %lld\n",v,u,t);
    ret+=t;
    printf("%lld\n",ret%P);
}
///
void init();
int main()
{
    init();
    //printf("\t%lld\n",query(sid[3],sid[3],1,N,1));
    for(int i=1;i<=M;++i)
    {
        int q;
        scanf("%d",&q);
        switch(q)
        {
            case 4:tree_query();break;
            case 3:tree_add();break;
            case 2:chain_query();break;
            case 1:chain_add();break;
        }
    }
    return 0;
}
void init()
{
    scanf("%d%d%d%d",&N,&M,&R,&P);
    for(int i=1; i<=N; ++i)
        scanf("%lld",a+i);
    for(int i=1; i<=N-1; ++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
        addEdge(y,x);
    }
    dep[R]=1;
    dfs1(R);
    dfs2(R,R);
    build_tree(1,N,1);
}

树网的核

树网的核

题目链接:https://www.luogu.org/problem/show?pid=1099

题目大意

​ 给你一棵树,定义最长的路径为直径,在直径上选取长不超过S的一段,问所有选取方式中其他所有点的距离最大值最小是多少.

分析

​ 在直径D上选取一段L,不妨令最长距离为dis(a,b),a属于L,b不属于L,如b不为D端点,则令D端点为x,y.那么min( dis(x,a),dis(y,a))<dis(b,a),把这一段接在上面可得更长的直径,前提不成立.

​ 所以可以单独分析直径D,将直径单独拿出分析,则可以当作一条链.用滑动窗口求解.

代码
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
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include<string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int inf=0x3f3f3f3f;
int N,S;
vector<int> mat[310];
int dis[310][310];
struct line
{
    int x,y,len;
    line(int _x,int _y,int _l){x=_x;y=_y;len=_l;}
};
vector<line> zj;//直径
vector<int> d;
bool vis[30010];
int ans=inf;
// code
void init()
{
    memset(dis,0x3f,sizeof dis);
    scanf("%d%d",&N,&S);
    for(int i=1; i<=N; ++i)
        dis[i][i]=0;
    for(int i=1; i<=N-1; ++i)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        dis[x][y]=dis[y][x]=v;
        mat[x].push_back(y);
        mat[y].push_back(x);
    }
}
void floyd()//求直径
{
    for(int k=1; k<=N; ++k)
        for(int i=1; i<=N; ++i)
            for(int j=1; j<=N; ++j)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
    int maxnum=0;
    for(int i=1; i<=N; ++i)
        for(int j=1; j<=N; ++j)
            if(dis[i][j]<1e9)
                maxnum=max(dis[i][j],maxnum);
    for(int i=1; i<=N; ++i)
        for(int j=i; j<=N; ++j)
            if(dis[i][j]==maxnum)
                zj.push_back(line(i,j,maxnum));
}
bool dfs(int cur,int end)
{
    vis[cur]=true;
    if(cur==end)
    {
        d.push_back(cur);
        return true;
    }
    for(int i=0; i<mat[cur].size(); ++i)
        if(!vis[mat[cur][i]]&&dfs(mat[cur][i],end))
        {
            d.push_back(cur);
            return true;
        }
    return false;
}
void solve()
{
    int pl=0,pr=0;//指针
    int up=d.size()-1;
    int st=d[0],ed=d[up]; 
    for(pl=0;pl<=up;++pl)
    {
        for(pr=pl;pr<=up&&dis[d[pr]][d[pl]]<=S;++pr) ;
        pr--;
        int minL= ( d[pl]==st? -inf: dis[d[pl]][st] );
        int minR= ( d[pr]==ed? -inf: dis[d[pr]][ed] );
        ans=min(ans,max(minL,minR));       
    }
}
void work()
{
    floyd();
    for(int i=0; i<zj.size(); ++i)
    {
        memset(vis,0,sizeof vis);
        d.clear();
        dfs(zj[i].x,zj[i].y);
        solve();
    }
    printf("%d",ans);
}
int main()
{
    init();
    work();
    return 0;
}

2^k进制数

2^k进制数

题目链接:https://www.luogu.org/problem/show?pid=1066

题目大意&分析

​ 把每一位看作是一个序列中的数,则总共有W/K或W/K+1个数:

  1. W%K==0 (W/K)

    可以看到,此时变成了求给定全集中不重子序列数量,考虑组合数公式,使用高精的杨辉三角推得结果.

  2. W%K!=0 (W/K+1)

    枚举第一位(有位数限制),因为这是一个升序排列,所以后方元素会受到限制,即给定全集不同,其余同上.

代码
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
/**
进制数
Luogu P1066
AC
*/
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int K,W;
int yh[520][520][60];//万进制
const int lendit=58;
int ans[60];
int t[60];
// code
void initNum(int *a)
{
    a[lendit]=1;
}
void display(int *a)
{
    printf("%d",a[a[lendit]-1]);
    for(int i=a[lendit]-2; i>=0; --i)
    {
        printf("%04d",a[i]);
    }
    printf(" ");
}
void add(int *a,int *b,int *out)//万进制高精
{
    int len=max(max(out[lendit],a[lendit]),b[lendit]);
    out[lendit]=len;
    for(int i=0; i<len; ++i)
    {
        out[i]+=(a[i]+b[i]);
        if(out[i]>=10000)
        {
            int t=out[i]/10000;
            out[i]%=10000;
            out[i+1]+=t;
        }
    }
    if(out[out[lendit]]!=0) ++out[lendit];
}
void init()
{
    scanf("%d%d",&K,&W);
    for(int i=0; i<=(1<<K)+4; ++i)
        for(int j=0; j<=(1<<K)+4; ++j)
            initNum(yh[i][j]);
    initNum(t);
    initNum(ans);
    yh[1][1][0]=1;
    for(int i=2; i<=(1<<K)+4; ++i)
        for(int j=1; j<=i; ++j)
            add(yh[i-1][j-1],yh[i-1][j],yh[i][j]);
}
void work()
{
    for(int i=2; i*K<=W; ++i)
        if(((1<<K)-1)>=i)
            add(t,yh[(1<<K)+1-1][i+1],ans);
    int hdit=(1<<(W%K));
    for(int i=1; i<hdit; ++i)
        if(((1<<K)-1-i)>=(W/K))
            add(t,yh[(1<<K)-1-i  +1][W/K+1],ans);
    display(ans);
}
int main()
{
    init();
    work();
    return 0;
}