Description

You are given a tree (an acyclic undirected connected graph) with  n nodes. The tree nodes are numbered from 1 to  n.

Each node has a color, white or black, and a weight.

We will ask you to perfrom some instructions of the following form:

  • u : ask for the maximum weight among the nodes which are connected to u, two nodes are connected iff all the node on the path from u to v (inclusive u and v) have a same color.
  • u : toggle the color of u(that is, from black to white, or from white to black).
  • u w: change the weight of u to w.
 

Input

The first line contains a number n denoted how many nodes in the tree(1 ≤ n ≤ 105). The next n - 1 lines, each line has two numbers (u,  v) describe a edge of the tree(1 ≤ u,  v ≤ n).

The next 2 lines, each line contains n number, the first line is the initial color of each node(0 or 1), and the second line is the initial weight, let's say Wi, of each node(|Wi| ≤ 109).

The next line contains a number m denoted how many operations we are going to process(1 ≤ m ≤ 105). The next m lines, each line describe a operation (t,  u) as we mentioned above(0 ≤ t ≤ 2, 1 ≤ u ≤ n, |w| ≤ 109).

 

Output

For each query operation, output the corresponding result.

 

Sample Input

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

Sample Output

1
5
 
题解:
http://www.cnblogs.com/chenyushuo/p/5228875.html 这个相似,不过要用set维护通过虚边相连的点的最大权值,lct维护这条链上的最大值。
code:
 #include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
char ch;
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
const int maxn=;
const int maxm=;
int n,q,op,a,b,v,tot,now[maxn],son[maxm],pre[maxm],fa[maxn],col[maxn];
struct lct{
int id,fa[maxn],son[maxn][],val[maxn],maxv[maxn];
multiset<int> rest[maxn];
int which(int x){return son[fa[x]][]==x;}
bool isroot(int x){return son[fa[x]][]!=x&&son[fa[x]][]!=x;}
void update(int x){
maxv[x]=val[x];
if (!rest[x].empty()) maxv[x]=max(maxv[x],*rest[x].rbegin());
if (son[x][]) maxv[x]=max(maxv[x],maxv[son[x][]]);
if (son[x][]) maxv[x]=max(maxv[x],maxv[son[x][]]);
}
void rotate(int x){
int y=fa[x],z=fa[y],d=which(x),dd=which(y);
fa[son[x][d^]]=y,son[y][d]=son[x][d^],fa[x]=fa[y];
if (!isroot(y)) son[z][dd]=x;
fa[y]=x,son[x][d^]=y,update(y),update(x);
}
void splay(int x){
while (!isroot(x)){
if (isroot(fa[x])) rotate(x);
else if (which(x)==which(fa[x])) rotate(fa[x]),rotate(x);
else rotate(x),rotate(x);
}
}
void access(int x){
for (int p=;x;x=fa[x]){
splay(x);
if (son[x][]) rest[x].insert(maxv[son[x][]]);
if (p) rest[x].erase(rest[x].find(maxv[p]));
son[x][]=p,update(p=x);
}
}
void link(int x,int y){
if (!y) return;
access(y),splay(y),splay(x),fa[x]=y,son[y][]=x,update(y);
}
void cut(int x,int y){
if (!y) return;
access(x),splay(x),fa[son[x][]]=,son[x][]=,update(x);
}
int find_root(int x){for (access(x),splay(x);son[x][];x=son[x][]); return x;}
void query(int x){
int t=find_root(x); splay(t);
printf("%d\n",col[t]==id?maxv[t]:maxv[son[t][]]);
}
void modify(int x,int v){access(x),splay(x),val[x]=v,update(x);}
}T[];
void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void add(int a,int b){put(a,b),put(b,a);}
void dfs(int u){
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if (v!=fa[u]) fa[v]=u,T[col[v]].link(v,u),dfs(v);
}
int main(){
read(n),T[].id=,T[].id=;
for (int i=;i<n;i++) read(a),read(b),add(a,b);
for (int i=;i<=n;i++) read(col[i]);
for (int i=;i<=n;i++) read(T[].val[i]),T[].maxv[i]=T[].val[i];
for (int i=;i<=n;i++) T[].maxv[i]=T[].val[i]=T[].val[i];
dfs();
for (read(q);q;q--){
read(op),read(a);
if (op==) T[col[a]].query(a);
else if (op==) T[col[a]].cut(a,fa[a]),col[a]^=,T[col[a]].link(a,fa[a]);
else read(v),T[].modify(a,v),T[].modify(a,v);
}
return ;
}

bzoj3639: Query on a tree VII的更多相关文章

  1. BZOJ 3639: Query on a tree VII

    Description 一棵树,支持三种操作,修改点权,修改颜色,问所有与他路径上颜色相同的点的最大权,包含这两个点. Sol LCT. 用LCT来维护重边,对于每个节点在建一个set用来维护轻边,这 ...

  2. 2019.02.17 spoj Query on a tree VII(链分治)

    传送门 跟QTREE6QTREE6QTREE6神似,改成了求连通块里的最大值. 于是我们对每条链开一个heapheapheap维护一下即可. MDMDMD终于1A1A1A链分治了. 代码: #incl ...

  3. SP16580 QTREE7 - Query on a tree VII

    Description 一棵树,每个点初始有个点权和颜色(0/1) 0 u :询问所有u,v 路径上的最大点权,要满足u,v 路径上所有点的颜色都相同 1 u :反转u 的颜色 2 u w :把u 的 ...

  4. BZOJ 3639: Query on a tree VII LCT_set维护子树信息

    用 set 维护子树信息,细节较多. Code: #include <cstring> #include <cstdio> #include <algorithm> ...

  5. 洛谷SP16580 QTREE7 - Query on a tree VII(LCT,multiset)

    洛谷题目传送门 思路分析 维护子树最值还是第一次写QwQ 因为子树的最值会变化,所以不能简单地把最值记下来,还要维护一个平衡树,把每个子树的最大值扔进去,来资磁插入.删除和查询最值. 然后我就懒得手写 ...

  6. SP16580 QTREE7 - Query on a tree VII(LCT)

    题意翻译 一棵树,每个点初始有个点权和颜色(输入会给你) 0 u:询问所有u,v路径上的最大点权,要满足u,v路径上所有点颜色相同 1 u:反转u的颜色 2 u w:把u的点权改成w 题解 Qtree ...

  7. HDU 6191 Query on A Tree(字典树+离线)

    Query on A Tree Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Othe ...

  8. Query on a tree——树链剖分整理

    树链剖分整理 树链剖分就是把树拆成一系列链,然后用数据结构对链进行维护. 通常的剖分方法是轻重链剖分,所谓轻重链就是对于节点u的所有子结点v,size[v]最大的v与u的边是重边,其它边是轻边,其中s ...

  9. SPOJ 375. Query on a tree (树链剖分)

    Query on a tree Time Limit: 5000ms Memory Limit: 262144KB   This problem will be judged on SPOJ. Ori ...

随机推荐

  1. 搭建apache http服务器

    异步: http://blog.csdn.net/lzhlzz/article/details/39496285

  2. 第五届山东ACM大赛汇总

    A.angry_birds_again_and_again 简单积分: http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem& ...

  3. 【hadoop2.6.0】安装+例子运行

    由于下载的是hadoop的最新版,网上各种杂七杂八的东西都不适用.好在官网上说的也够清楚了.如果有人看这篇文章的话,最大的忠告就是看官网. 官网2.6.0的安装教程:http://hadoop.apa ...

  4. sqlmap遇到url重写的示例

    url_rewrite 这个问题 国内外的坛子里都有人问. D:\cygwin\pentest\database\sqlmap\doc \faq.pdf 下面是官方给的解答. 1.15 How to ...

  5. Codeforces Round #365 (Div. 2) A 水

    A. Mishka and Game time limit per test 1 second memory limit per test 256 megabytes input standard i ...

  6. 多路转接之poll和select

    先看poll(): #include <stdio.h> #include <stdlib.h> #include <string.h> #include < ...

  7. HTML5 改良的 input 元素的种类

    html5中增加改良的input 元素 . 在过去我们制作网页输入框,会用到不少JS验证,如今有了HTML5写这种效果已经没有那么麻烦了,下面我来给大家介绍两种HTML5的input的新增加的类型应用 ...

  8. idea其他人把jar更新之后更新不到

    昨天下午开始就发现这个问题,其他同事把jar更新了之后,我一直获取不到更新之后的内容.尝试了很多方法,删除具体的更新不到的jar,一直不停的mvn clean install -U -Dmaven.t ...

  9. Liunx下Intel无线网卡驱动安装

    原文: https://blog.csdn.net/u014157776/article/details/78272611 首先查看网卡型号,指令: lspci | grep -i net 如果是In ...

  10. TabHost实现通话记录界面

    //MainActivity.java   public class MainActivity extends TabActivity   {       @Override       public ...