首页 > 其他分享 >U41492 树上数颜色 题解

U41492 树上数颜色 题解

时间:2024-02-19 17:48:45浏览次数:26  
标签:颜色 tong int 题解 U41492 tr maxn 树上 fl

U41492 树上数颜色

题目描述

给一棵根为1的树,每次询问子树颜色种类数

输入格式

第一行一个整数n,表示树的结点数

接下来n-1行,每行一条边

接下来一行n个数,表示每个结点的颜色c[i]

接下来一个数m,表示询问数

接下来m行表示询问的子树

输出格式

对于每个询问,输出该子树颜色数

输入输出样例

输入 #1复制

5

1 2

1 3

2 4

2 5

1 2 2 3 3

5

1

2

3

4

5

输出 #1复制

3

2

1

1

1

说明/提示

对于前三组数据,有1≤m,c[i]≤n≤100

而对于所有数据,有1≤m,c[i]≤n≤1e5

暴力算法 ac

#include<iostream>
#include<vector>
using namespace std;
const int maxn=1e5+10;
vector<int> tr[maxn];
int tong[maxn],ans[maxn],c[maxn],fa[maxn],now;
void calc(int u,int f,int fl)
{
	tong[c[u]]+=fl;
	if (fl==1&&tong[c[u]]==1) now++;
	if (fl==-1&&tong[c[u]]==0) now--;
	for (int i=0;i<tr[u].size();i++)
	{
		int v=tr[u][i];
		if (v==f) continue;
		calc(v,u,fl);
	}
}
void dfs(int u,int f)
{
	for (int i=0;i<tr[u].size();i++)
	{
		int v=tr[u][i];
		if (v==f) continue;
		dfs(v,u);
	}
	calc(u,f,1);
	ans[u]=now;
	calc(u,f,-1);
}
int main()
{
	int n,m;
	cin>>n;
	for (int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		tr[x].push_back(y);
		tr[y].push_back(x);
	}
	for (int i=1;i<=n;i++) cin>>c[i];
	dfs(1,0);
	cin>>m;
	while(m--)
	{
		int x;
		cin>>x;
		cout<<ans[x]<<endl;	 
	} 
}

  

标签:颜色,tong,int,题解,U41492,tr,maxn,树上,fl
From: https://www.cnblogs.com/smghj/p/18021588

相关文章

  • P2524 Uim的情人节礼物•其之弐 题解
    题目描述前传:详见洛谷P2525Uim成功地按照顺序将礼物送到了 N 个妹子的手里并维持她们的和谐。现在Uim现在想知道,他最终选择的顺序是所有给 N 个妹子送礼顺序中,字典序第几小的。送礼顺序可以看作1,2,⋯,N 的一个排列。输入格式第一行一个整数N,表示有 N 个数。第二......
  • P3411 序列变换 题解
    自己做不出来,看现在题解区的题解讲的都不咋清楚。懂了之后来为后人铺路。而且我的马蜂比较好看题目传送门我能看懂这道题,主要是依靠了这篇题解的帮助。首先我们只关注数的相对关系,所以可以离散化。注意到值域\(10^6\),用数组离散化。这道题可以用贪心做。(有一些定义先往下看)......
  • P5914 MOS 题解
    一道练习贪心证明的好题。绝大多数题解只是点出了以下结论:要么最快的带最慢的;要么最慢的带次慢的。并没有给出证明。我就补上这个证明。为了证明这个贪心结论,我们先证明几个引理。引理一:每次将火把带回来的,一定是对岸最快的。引理一证明:如果回来的不是对岸最快的,让对岸最......
  • CF167B题解
    CF167B这里更容易进入且有翻译题意给定初始背包容量\(k\),要进行\(n\)场比赛,每场比赛有\(p_i\%\)的概率能够胜利,赢的一场比赛能获得一个奖励——当\(a_i=-1\)时获得一个体积为\(1\)的奖品,或者当\(a_i>0\)时给背包增加\(a_i\)容量,求所有比赛结束后至少赢得\(......
  • 理想的正方形——题解
    题目描述一看正方形,得,二维数组,单调队列。单调队列可以将一个区间最大值存储,所以只需要根据给定的正方形长度先横着推一遍,再竖着推一遍,将正方形中的最大值和最小值都储存在正方形右下角方格,最后遍历即可。先以行储存以k为长度的最大/小值;再以剩下k-m横向长度的最值向下扩展k个......
  • 跨域问题解决
    跨域举例A网站部署在localhost:63343请求loocalhost:8080/api/user/add,就会出现跨域问题。同源策略同源策略:协议,主机,端口,只有这三者全部相同时,才可以相互访问。现在接口地址为101.10.11.1X:8081,请判断以下哪些可以通过:访问地址描述结果https://127.0.0.1:808......
  • 数列的异或和(题解)
    题目样例样例输入5512345113135036113135样例输出0257二进制运算二进制运算的优先级小于四则运算,所以在与四则运算同时出现时,注意加括号按位与(&)在二进制下,相同位的数都为1时,这一位的结果为1,任意一个不是1或都是0,则为0(eg:0100110&0010111=000......
  • 场景问题解决方法
    1.tomcatspringboot通过域名访问时直接跳到127.0.0.1的问题这种情况极可能是因为 server.xml配置问题导致,可以参考这篇文章tomcat设置http代理详细教程-知乎(zhihu.com)2.如何访问内网中所有的服务和站点要访问一个内网中所有的服务和站点(如内网的所有网站和数据库等),......
  • think-cell Round 1 题解 (A~F)
    think-cellRound1.目录A.MaximiseTheScore排序后输出所有奇数位之和.B.PermutationPrinting\(1,n,2,n-1\cdots\).C.LexicographicallyLargest注意到对于一个\(a_i\)来说\([a_i+1,a_i+i]\)中的所有数都可以被选中,那么问题变给若干区间,每个区间选一个数要......
  • [ARC122E] Increasing LCMs 题解
    Description给定长度为\(N\)的正整数序列\(\{A_i\}\),满足\(A_i\)单调升。问是否能将\(\{A_i\}\)重排为序列\(\{x_i\}\),满足:令\(y_i=\operatorname{LCM}(x_1,\dots,x_i)\),\(\forall1\lei<N,y_i<y_{i+1}\)(即\(y_i\)单调升)。$1\\leq\N\\leq\......