深圳最好的营销网站建设公司排名,免费建站工具,网站建站建设首选上海黔文信息科技有限公司2,酒泉网站seo题意#xff1a;
染色问题#xff1a;给一个固定结构的树#xff0c;现在有两个操作#xff1a; #xff08;1#xff09; y 将结点x及其所有后代结点染成颜色y#xff1b; #xff08;2#xff09;查询结点x当前的颜色。 其实就是区间染色问题#xff0c;不过需要d…题意
染色问题给一个固定结构的树现在有两个操作 1 y 将结点x及其所有后代结点染成颜色y 2查询结点x当前的颜色。 其实就是区间染色问题不过需要dfs预处理
题目
There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody’s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
Input
The first line contains a single positive integer T( T 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1u,vN).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
“C x” which means an inquiry for the current task of employee x
or
T x ywhich means the company assign task y to employee x.
(1xN,0y10^9)
Output
For each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.
Sample Input
1 5 4 3 3 2 1 3 5 2 5 C 3 T 2 1 C 3 T 3 2 C 3
Sample Output
Case #1: -1 1 2
分析
1.由于题目给的是一个固定的树所以我们需要对它进行处理使之成为我们好处理的区间问题。 2.关于预处理我采用的是先用vector容器进行存边之后dfs用两个数组分别存储以某点为“”祖宗节点“”的区间起始类似时间戳的思想将某个点的编号 3.预处理之后就是线段树模板啦嘿嘿这个没啥好说的这里不再赘述 区间修改单点查询
AC代码
#includestdio.h
#includestring.h
#includevector
#includealgorithm
using namespace std;
const int M5e410;
int t,n,m,ans,a,b,k;
vectorintve[M];
int L[M],R[M],dp[M2],lazy[M2];
bool vis[M];
char s[5];
void dfs(int x)
{L[x]ans;for(int i0; ive[x].size(); i)dfs(ve[x][i]);R[x]ans;
}
void pushdown(int x)
{if(lazy[x]){lazy[x1]lazy[x1|1]lazy[x];dp[x1]dp[x1|1]dp[x];lazy[x]0;}
}
void update(int mi,int ma,int l,int r,int x,int value)
{if(lmirma){dp[x]lazy[x]value;return;}pushdown(x);int mid(lr)1;if(midmi)update(mi,ma,l,mid,x1,value);if(midma)update(mi,ma,mid1,r,x1|1,value);
}
int query(int now,int l,int r,int x)//单点修改
{if(lr)return dp[x];pushdown(x);int mid(lr)1;if(midnow)return query(now,l,mid,x1);elsereturn query(now,mid1,r,x1|1);
}
int main()
{scanf(%d,t);k0;while(t--){ans0;memset(dp,-1,sizeof(dp));memset(lazy,0,sizeof(lazy));memset(vis,false,sizeof(vis));scanf(%d,n);for(int i1; in; i)ve[i].clear();for(int i0; in-1; i){int u,v;scanf(%d%d,u,v);ve[v].push_back(u);//接下来的N-1行每行包含两个整数u和v这表示雇员v是雇员u1 uv N的直接老板。vis[u]true;}for(int i1; in; i)if(!vis[i])dfs(i);scanf(%d,m);printf(Case #%d:\n,k);while(m--){scanf(%s,s);if(s[0]C){scanf(%d,a);printf(%d\n,query(L[a],1,ans,1));}else{scanf(%d%d,a,b);update(L[a],R[a],1,ans,1,b);}}}return 0;
}
备战ing题目分析简略见谅转载请注明出处。。。。。
