POJ 3237：Tree

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题目大意
题解
代码

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

CHANGEi v	Change the weight of the ith edge to v
NEGATEa b	Negate the weight of every edge on the path from a to b
QUERYa b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.
Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and bwith weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

Sample Output

1
3

题目大意

给你一颗树，要求支持下列3个操作：
1.Q-询问两点之间路径的边中边权最大的；
2.N-把两点之间的路径的边权全部取反；
3.C-修改某条边的边权。

题解

这道题目用树链剖分，才开始学习树链剖分，这一题调了许久，结果最后发现是Query线段树的Tag没有下传。
这道题线段树只需要维护一下最大值和最小值，然后取反操作就是最大值和最小值都取反，然后交换最大值最小值【稍微脑补一下】

代码

/*Author:WNJXYK*/
#include<cstdio>
#include<cstring>
using namespace std;
const int Inf=1<<30;
const int Maxn=100010;
int siz[Maxn+5],son[Maxn+5],dep[Maxn+5],fa[Maxn+5],w[Maxn+5],top[Maxn+5];
int totw=0;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int a,int b){
        v=a;nxt=b;
    }
};
Edge e[2*Maxn+5];
int nume=0;
int head[Maxn+5];
struct Input{
    int x,y,w;
    Input(){}
    Input(int a,int b,int c){
        x=a;y=b;w=c;
    }
};
Input inp[Maxn+5];
struct Btree{
    int left,right;
    int max,min;
    int tag;
};
Btree tree[Maxn*5+5];
inline int remax(int a,int b){
    if (a>b) return a;
    return b;
}
inline int remin(int a,int b){
    if (a<b) return a;
    return b;
}
inline void swap(int &x,int &y){
    int tmp=x;
    x=y;
    y=tmp;
}
void _build(int x,int left,int right){
    tree[x].left=left;tree[x].right=right;
    tree[x].max=0;tree[x].min=0;tree[x].tag=0;
    if (tree[x].left==tree[x].right) return ;
    int mid=(left+right)/2;
    _build(x*2,left,mid);_build(x*2+1,mid+1,right);
}
inline void _reserve_TreeNode(int x){
    tree[x].max=-tree[x].max;
    tree[x].min=-tree[x].min;
    swap(tree[x].min,tree[x].max);
}
inline void _clean(int x){
    if (tree[x].tag==0 || tree[x].left==tree[x].right) return;
    _reserve_TreeNode(x*2);_reserve_TreeNode(x*2+1);
    tree[x*2].tag^=1;tree[x*2+1].tag^=1;tree[x].tag=0;
}
inline void _update(int x){
    tree[x].min=remin(tree[x*2].min,tree[x*2+1].min);
    tree[x].max=remax(tree[x*2].max,tree[x*2+1].max);
}
void _change(int x,int pos,int val){
    _clean(x);
    if (tree[x].left==tree[x].right){
        tree[x].min=tree[x].max=val;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (pos<=mid) _change(x*2,pos,val);
        if (pos>mid) _change(x*2+1,pos,val);
        _update(x);
    }
}
void _reserve(int x,int left,int right){
    _clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        _reserve_TreeNode(x);tree[x].tag^=1;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid) _reserve(x*2,left,right);
        if (right>mid) _reserve(x*2+1,left,right);
        _update(x);
    }
}
int _query(int x,int left,int right){
    _clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        return tree[x].max;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        int res=-Inf;
        if (left<=mid) res=remax(res,_query(x*2,left,right));
        if (right>mid) res=remax(res,_query(x*2+1,left,right));
        return res;
    }
}
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}
void dfs_1(int x){
    siz[x]=1;son[x]=0;
    for (int i=head[x];i;i=e[i].nxt){
        if (fa[x]!=e[i].v){
            fa[e[i].v]=x;
            dep[e[i].v]=dep[x]+1;
            dfs_1(e[i].v);
            if (siz[e[i].v]>siz[son[x]]) son[x]=e[i].v;
            siz[x]+=siz[e[i].v];
        }
    }
}
void dfs_2(int x,int tp){
    w[x]=++totw;top[x]=tp;
    if (son[x]!=0) dfs_2(son[x],tp);
    for (int i=head[x];i;i=e[i].nxt){
        if (e[i].v!=son[x] && e[i].v!=fa[x]){
            dfs_2(e[i].v,e[i].v);
        }
    }
}
inline int query(int u,int v){
    int res=-Inf;
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        //printf("%d %dn",f1,f2);
        if (dep[f1]<dep[f2]){
            swap(f1,f2);swap(u,v);
        }
        res=remax(res,_query(1,w[f1],w[u]));
        u=fa[f1];f1=top[u];
    }
    if (u==v) return res;
    if (dep[u]>dep[v]) swap(u,v);
    return remax(res,_query(1,w[son[u]],w[v]));
}
inline void reserve(int u,int v){
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if (dep[f1]<dep[f2]){
            swap(f1,f2);swap(u,v);
        }
        _reserve(1,w[f1],w[u]);
        u=fa[f1];f1=top[u];
    }
    if (u==v) return;
    if (dep[u]>dep[v]) swap(u,v);
    _reserve(1,w[son[u]],w[v]);
}
int T;
int n;
int main(){
    freopen("In.txt","r",stdin);
    freopen("Out.txt","w",stdout);
    scanf("%d",&T);
    for (;T--;){
        scanf("%d",&n);
        _build(1,0,n);
        memset(head,0,sizeof(head));
        memset(son,0,sizeof(son));
        nume=0;totw=0;
        fa[1]=1;dep[1]=1;
        for (int i=1;i<n;i++){
            scanf("%d%d%d",&inp[i].x,&inp[i].y,&inp[i].w);
            addEdge(inp[i].x,inp[i].y);
        }
        dfs_1(1);dfs_2(1,1);
        for (int i=1;i<n;i++){
            if (dep[inp[i].x]>dep[inp[i].y])
                swap(inp[i].x,inp[i].y);
            _change(1,w[inp[i].y],inp[i].w);
        }
        char ch[10];
        int x,y;
        while(scanf("%s",&ch)!=EOF){
            if (ch[0]=='D') break;
            scanf("%d%d",&x,&y);
            if (ch[0]=='Q') printf("%dn",query(x,y));
            if (ch[0]=='C') _change(1,w[inp[x].y],y);
            if (ch[0]=='N') reserve(x,y);
        }
    }
    return 0;
}

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

/*Author:WNJXYK*/

#include<cstdio>

#include<cstring>

using namespace std;

const int Inf=1<<30;

const int Maxn=100010;

int siz[Maxn+5],son[Maxn+5],dep[Maxn+5],fa[Maxn+5],w[Maxn+5],top[Maxn+5];

int totw=0;

struct Edge{

int v,nxt;

Edge(){}

Edge(int a,int b){

v=a;nxt=b;

}

};

Edge e[2*Maxn+5];

int nume=0;

int head[Maxn+5];

struct Input{

int x,y,w;

Input(){}

Input(int a,int b,int c){

x=a;y=b;w=c;

}

};

Input inp[Maxn+5];

struct Btree{

int left,right;

int max,min;

int tag;

};

Btree tree[Maxn*5+5];

inline int remax(int a,int b){

if (a>b) return a;

return b;

}

inline int remin(int a,int b){

if (a<b) return a;

return b;

}

inline void swap(int &x,int &y){

int tmp=x;

x=y;

y=tmp;

}

void _build(int x,int left,int right){

tree[x].left=left;tree[x].right=right;

tree[x].max=0;tree[x].min=0;tree[x].tag=0;

if (tree[x].left==tree[x].right) return ;

int mid=(left+right)/2;

_build(x*2,left,mid);_build(x*2+1,mid+1,right);

}

inline void _reserve_TreeNode(int x){

tree[x].max=-tree[x].max;

tree[x].min=-tree[x].min;

swap(tree[x].min,tree[x].max);

}

inline void _clean(int x){

if (tree[x].tag==0 || tree[x].left==tree[x].right) return;

_reserve_TreeNode(x*2);_reserve_TreeNode(x*2+1);

tree[x*2].tag^=1;tree[x*2+1].tag^=1;tree[x].tag=0;

}

inline void _update(int x){

tree[x].min=remin(tree[x*2].min,tree[x*2+1].min);

tree[x].max=remax(tree[x*2].max,tree[x*2+1].max);

}

void _change(int x,int pos,int val){

_clean(x);

if (tree[x].left==tree[x].right){

tree[x].min=tree[x].max=val;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (pos<=mid) _change(x*2,pos,val);

if (pos>mid) _change(x*2+1,pos,val);

_update(x);

}

void _reserve(int x,int left,int right){

_clean(x);

if (left<=tree[x].left && tree[x].right<=right){

_reserve_TreeNode(x);tree[x].tag^=1;

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (left<=mid) _reserve(x*2,left,right);

if (right>mid) _reserve(x*2+1,left,right);

_update(x);

}

int _query(int x,int left,int right){

_clean(x);

if (left<=tree[x].left && tree[x].right<=right){

return tree[x].max;

}else{

int mid=(tree[x].left+tree[x].right)/2;

int res=-Inf;

if (left<=mid) res=remax(res,_query(x*2,left,right));

if (right>mid) res=remax(res,_query(x*2+1,left,right));

return res;

}

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);

head[u]=nume;

e[++nume]=Edge(u,head[v]);

head[v]=nume;

}

void dfs_1(int x){

siz[x]=1;son[x]=0;

for (int i=head[x];i;i=e[i].nxt){

if (fa[x]!=e[i].v){

fa[e[i].v]=x;

dep[e[i].v]=dep[x]+1;

dfs_1(e[i].v);

if (siz[e[i].v]>siz[son[x]]) son[x]=e[i].v;

siz[x]+=siz[e[i].v];

}

void dfs_2(int x,int tp){

w[x]=++totw;top[x]=tp;

if (son[x]!=0) dfs_2(son[x],tp);

for (int i=head[x];i;i=e[i].nxt){

if (e[i].v!=son[x] && e[i].v!=fa[x]){

dfs_2(e[i].v,e[i].v);

}

inline int query(int u,int v){

int res=-Inf;

int f1=top[u],f2=top[v];

while(f1!=f2){

//printf("%d %dn",f1,f2);

if (dep[f1]<dep[f2]){

swap(f1,f2);swap(u,v);

}

res=remax(res,_query(1,w[f1],w[u]));

u=fa[f1];f1=top[u];

}

if (u==v) return res;

if (dep[u]>dep[v]) swap(u,v);

return remax(res,_query(1,w[son[u]],w[v]));

}

inline void reserve(int u,int v){

int f1=top[u],f2=top[v];

while(f1!=f2){

if (dep[f1]<dep[f2]){

swap(f1,f2);swap(u,v);

}

_reserve(1,w[f1],w[u]);

u=fa[f1];f1=top[u];

}

if (u==v) return;

if (dep[u]>dep[v]) swap(u,v);

_reserve(1,w[son[u]],w[v]);

}

int T;

int n;

int main(){

freopen("In.txt","r",stdin);

freopen("Out.txt","w",stdout);

scanf("%d",&T);

for (;T--;){

scanf("%d",&n);

_build(1,0,n);

memset(head,0,sizeof(head));

memset(son,0,sizeof(son));

nume=0;totw=0;

fa[1]=1;dep[1]=1;

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

scanf("%d%d%d",&inp[i].x,&inp[i].y,&inp[i].w);

addEdge(inp[i].x,inp[i].y);

}

dfs_1(1);dfs_2(1,1);

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

if (dep[inp[i].x]>dep[inp[i].y])

swap(inp[i].x,inp[i].y);

_change(1,w[inp[i].y],inp[i].w);

}

char ch[10];

int x,y;

while(scanf("%s",&ch)!=EOF){

if (ch[0]=='D') break;

scanf("%d%d",&x,&y);

if (ch[0]=='Q') printf("%dn",query(x,y));

if (ch[0]=='C') _change(1,w[inp[x].y],y);

if (ch[0]=='N') reserve(x,y);

}

return 0;

}

WNJXYKの博客

喂你脚下有坑

POJ 3237：Tree

Description

Input

Output

Sample Input

Sample Output

题目大意

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

2022年 5月
一	二	三	四	五	六	日
						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

POJ 3237：Tree

Description

Input

Output

Sample Input

Sample Output

题目大意

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗