gym101138J(树链剖分,线段树维护区间连续子段最大和,好题)

101 阅读 0 评论 67 点赞

我是靠谱客的博主土豪大雁，这篇文章主要介绍gym101138J(树链剖分,线段树维护区间连续子段最大和,好题)，现在分享给大家，希望可以做个参考。

The Valentina's birthday is coming soon! Her parents love her so much that they are preparing some gifts to give her. Valentina is cute and smart and her parents are planning to set an interesting task for her.

They prepared a tree (a connected graph without cycles) with one gift in each vertex. Vertices are numbered 1 through n and the i-th of them contains a gift with value gi (a value describing Valentina's happiness if she gets a gift from this vertex). All gifts are wrapped so Valentina doesn't know their values.

Note that gi may be negative and it would mean that Valentina doesn't like the gift (do you remember when your parents gave you clothes or toys not adequate to your interests?).

Let's consider the following process:

Valentina chooses two vertices a and b (not necessarily distinct).
She unpacks all gifts on the path connecting a and b and thus she sees their values.
She chooses some part of the path connecting a and b. The chosen part must be connected and can't be empty (hence, it must be a path).
Valentina takes all gifts in the chosen part of the path and her total happiness is equal to the sum of the values of taken gifts.

Valentina is smart and for chosen a and b she will choose a part resulting in the biggest total happiness.

In order to maximize her chance to get a good bunch of gifts, parents allow her to ask q questions, each with two numbers a and b. For each Valentina's question parents will tell her the answer, i.e. the maximum total happiness for chosen a and b.

They noticed that answering Valentina's questions is an interesting problem. They want to know if you are smart enough to correctly answer all questions.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 105) — the size of the tree.

Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of two vertices connected with an edge. The given edges are guaranteed to describe a tree.

The next line contains n integers g1, g2, ... gn ( - 109 ≤ gi ≤ 109).

Then, the questions are given. One line contains an integer q (1 ≤ q ≤ 500 000) — the number of questions.

Finally, each of the last q lines contains two integers ai and bi (1 ≤ ai, bi ≤ n), describing one question.

Output

For each of the q questions find the maximum happiness of Valentina if she has to choose a non-empty part of the given path. For every question print the answer in a separate line.

   Examples 
 

     input 
   
复制代码6
1 2
1 3
1 4
4 5
4 6
-1 2 2 -2 5 8
6
2 5
2 3
1 5
5 3
1 4
5 6
6
1 2
1 3
1 4
4 5
4 6
-1 2 2 -2 5 8
6
2 5
2 3
1 5
5 3
1 4
5 6

     output 
   
复制代码5
3
5
5
-1
115
3
5
5
-1
11

题意：

给出n个点的一棵树，每个结点有个权值，m个查询，每个查询给出两个点u和v，查询u到v路径上最大连续和。

题解：

先树链剖分，在线段树中维护最大连续子段和，那么合并的时候还需要记录区间总和，区间左部分连续最大和，区间右部分最大连续和。

与以往不同的是，查询操作时返回一个线段树的结点类型的数，以便在树链剖分查询时的合并和线段树查询操作的合并。

详细见代码：

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll inf=0x3ffffffffffff;
const ll mod=1000000007;
const int maxn=100000+100;
int head[maxn];
struct edge
{
    int from,to,next;
}e[maxn*2];   //
struct node
{
    int l,r;
    ll mx,sum,lm,rm;
    node(){
        mx=sum=lm=rm=-inf;
        return;
    }
}seg[maxn*4];
int tol=0;
void add(int u,int v)
{
    e[++tol].to=v,e[tol].next=head[u],head[u]=tol;
}

int pos;
int fa[maxn],top[maxn],son[maxn],num[maxn],p[maxn],dep[maxn],fp[maxn];
ll a[maxn];
node up(node ls,node rs)
{
    node t;
    t.l=ls.l,t.r=rs.r;
    t.mx=max(max(ls.mx,rs.mx),ls.rm+rs.lm);
    t.lm=max(ls.lm,ls.sum+rs.lm);
    t.rm=max(rs.rm,ls.rm+rs.sum);
    t.sum=ls.sum+rs.sum;
    return t;
}
void build(int i,int l,int r)
{
    seg[i].l=l,seg[i].r=r;
    if(l==r)
    {
        seg[i].sum=seg[i].mx=seg[i].lm=seg[i].rm=a[fp[l]];
        return;
    }
    int m=(l+r)/2;
    build(i*2,l,m),build(i*2+1,m+1,r);
    seg[i]=up(seg[i*2],seg[i*2+1]);
}
void dfs(int u,int f,int d)
{
    num[u]=1;
    fa[u]=f;
    dep[u]=d;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f) continue;
        dfs(v,u,d+1);
        if(son[u]==0||num[v]>num[son[u]])
            son[u]=v;
        num[u]+=num[v];
    }
}
void dfs2(int u,int sp)
{
    top[u]=sp;
    if(son[u])
    {
        p[u]=pos;
        fp[pos]=u;
        pos++;
        dfs2(son[u],sp);
    }
    else
    {
        p[u]=pos;
        fp[pos]=u;
        pos++;
        return;
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])
            dfs2(v,v);
    }
}

node query(int i,int l,int r)
{
    if(seg[i].l==l&&seg[i].r==r)
    {
        return seg[i];
    }
    int m=(seg[i].l+seg[i].r)/2;
    if(r<=m) return query(i*2,l,r);
    else if(l>m) return query(i*2+1,l,r);
    node t1=query(i*2,l,m),t2=query(i*2+1,m+1,r);
    return up(t1,t2);
}
ll find(int u,int v)
{
    int fu=top[u],fv=top[v];
    node tu,tv;         //
    bool f1=false,f2=false;
    while(fu!=fv)
    {
        if(dep[fu]>dep[fv])
        {
            if(f1)
            tu=up(query(1,p[fu],p[u]),tu);  //特别注意先后顺序,tu写在后面,后面的几个合并操作也是一样
            else tu=query(1,p[fu],p[u]),f1=true;
            u=fa[fu],fu=top[u];
        }
        else
        {
            if(f2) tv=up(query(1,p[fv],p[v]),tv);//
            else tv=query(1,p[fv],p[v]),f2=true;
            v=fa[fv],fv=top[v];
        }
    }
    if(dep[u]>dep[v])
    {
        if(f1)
        tu=up(query(1,p[v],p[u]),tu);
        else tu=query(1,p[v],p[u]);
    }
    else
    {
        if(f2)
            tv=up(query(1,p[u],p[v]),tv);
        else tv=query(1,p[u],p[v]);
    }
    swap(tu.lm,tu.rm);
    return up(tu,tv).mx;
}
void init()
{
    tol=0;pos=1;
    memset(head,0,sizeof(head));
    memset(fa,0,sizeof(fa));
    memset(son,0,sizeof(son));
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    rep(i,1,n)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    rep(i,1,n+1)
        scanf("%lld",&a[i]);
    dfs(1,0,0);
    dfs2(1,1);
    build(1,1,pos);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%lldn",find(u,v));
    }
    return 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
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll inf=0x3ffffffffffff;
const ll mod=1000000007;
const int maxn=100000+100;
int head[maxn];
struct edge
{
    int from,to,next;
}e[maxn*2];   //
struct node
{
    int l,r;
    ll mx,sum,lm,rm;
    node(){
        mx=sum=lm=rm=-inf;
        return;
    }
}seg[maxn*4];
int tol=0;
void add(int u,int v)
{
    e[++tol].to=v,e[tol].next=head[u],head[u]=tol;
}

int pos;
int fa[maxn],top[maxn],son[maxn],num[maxn],p[maxn],dep[maxn],fp[maxn];
ll a[maxn];
node up(node ls,node rs)
{
    node t;
    t.l=ls.l,t.r=rs.r;
    t.mx=max(max(ls.mx,rs.mx),ls.rm+rs.lm);
    t.lm=max(ls.lm,ls.sum+rs.lm);
    t.rm=max(rs.rm,ls.rm+rs.sum);
    t.sum=ls.sum+rs.sum;
    return t;
}
void build(int i,int l,int r)
{
    seg[i].l=l,seg[i].r=r;
    if(l==r)
    {
        seg[i].sum=seg[i].mx=seg[i].lm=seg[i].rm=a[fp[l]];
        return;
    }
    int m=(l+r)/2;
    build(i*2,l,m),build(i*2+1,m+1,r);
    seg[i]=up(seg[i*2],seg[i*2+1]);
}
void dfs(int u,int f,int d)
{
    num[u]=1;
    fa[u]=f;
    dep[u]=d;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==f) continue;
        dfs(v,u,d+1);
        if(son[u]==0||num[v]>num[son[u]])
            son[u]=v;
        num[u]+=num[v];
    }
}
void dfs2(int u,int sp)
{
    top[u]=sp;
    if(son[u])
    {
        p[u]=pos;
        fp[pos]=u;
        pos++;
        dfs2(son[u],sp);
    }
    else
    {
        p[u]=pos;
        fp[pos]=u;
        pos++;
        return;
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=son[u]&&v!=fa[u])
            dfs2(v,v);
    }
}

node query(int i,int l,int r)
{
    if(seg[i].l==l&&seg[i].r==r)
    {
        return seg[i];
    }
    int m=(seg[i].l+seg[i].r)/2;
    if(r<=m) return query(i*2,l,r);
    else if(l>m) return query(i*2+1,l,r);
    node t1=query(i*2,l,m),t2=query(i*2+1,m+1,r);
    return up(t1,t2);
}
ll find(int u,int v)
{
    int fu=top[u],fv=top[v];
    node tu,tv;         //
    bool f1=false,f2=false;
    while(fu!=fv)
    {
        if(dep[fu]>dep[fv])
        {
            if(f1)
            tu=up(query(1,p[fu],p[u]),tu);  //特别注意先后顺序,tu写在后面,后面的几个合并操作也是一样
            else tu=query(1,p[fu],p[u]),f1=true;
            u=fa[fu],fu=top[u];
        }
        else
        {
            if(f2) tv=up(query(1,p[fv],p[v]),tv);//
            else tv=query(1,p[fv],p[v]),f2=true;
            v=fa[fv],fv=top[v];
        }
    }
    if(dep[u]>dep[v])
    {
        if(f1)
        tu=up(query(1,p[v],p[u]),tu);
        else tu=query(1,p[v],p[u]);
    }
    else
    {
        if(f2)
            tv=up(query(1,p[u],p[v]),tv);
        else tv=query(1,p[u],p[v]);
    }
    swap(tu.lm,tu.rm);
    return up(tu,tv).mx;
}
void init()
{
    tol=0;pos=1;
    memset(head,0,sizeof(head));
    memset(fa,0,sizeof(fa));
    memset(son,0,sizeof(son));
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    rep(i,1,n)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    rep(i,1,n+1)
        scanf("%lld",&a[i]);
    dfs(1,0,0);
    dfs2(1,1);
    build(1,1,pos);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%lldn",find(u,v));
    }
    return 0;
}