`
huyifan951124
  • 浏览: 82881 次
社区版块
存档分类
最新评论

hihocoder 1156

 
阅读更多

题目大意:中文题。

算法思路:因为改变一个节点的颜色,只会影响到这个节点的父节点和子节点,所以,我们只需要在一开始建立好节点之间的关系maps[i][j](maps[i][j]表示第i个节点的子节点里颜色为j的节点个数),之后再没改变一个节点的颜色,就对该节点的父节点和和子节点进行操作即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define MAXN 100050
int t,n,m,d,q;
vector<int>v[MAXN];
int col[MAXN];
int par[MAXN];
map<int,int>maps[MAXN];
int main()
{

    scanf("%d",&t);
    int sym=1;
    while(t--)
    {
        memset(col,0,sizeof(col));
        scanf("%d",&n);
        int l,r;
        for(int i=1; i<=n; i++)
        {
            par[i]=i;
            v[i].clear();
            maps[i].clear();
        }
        for(int i=1; i<=n-1; i++)
        {
            scanf("%d%d",&l,&r);
            v[l].push_back(r);
            v[r].push_back(l);
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<v[i].size(); j++)
            {
                if(v[i][j]==par[i])
                    continue;
                maps[i][0]++;
                par[v[i][j]]=i;
            }
        }

        scanf("%d",&q);
        int flag,ans=1,x,y;
        printf("Case #%d:\n",sym++);
        while(q--)
        {

            scanf("%d",&flag);
            if(flag==1)
                printf("%d\n",ans);
            else
            {

                scanf("%d%d",&x,&y);
                if(col[x]==y)
                    continue;

                //对子节点
                ans-=maps[x][y];
                ans+=maps[x][col[x]];

                //对父节点
                if(par[x]!=x)
                {
                    if(y==col[par[x]])
                        ans--;
                    if(col[x]==col[par[x]])
                        ans++;
                    maps[par[x]][y]++;
                    maps[par[x]][col[x]]--;
                }
                col[x]=y;

            }



        }

    }
    return 0;
}




 

1
0
分享到:
评论

相关推荐

    hihocoder:hihocoder上的系列题解(http

    【描述】"#hihocoder hihocoder上的系列题解()" 提到的描述虽然简短,但表明这个资源可能是用户或社区成员在hihocoder上完成题目后整理的题解集合,可能是为了分享学习经验或者帮助其他学习者理解和解决同样的问题。...

    hihocoder week1 answer

    微软hiho coder平台第一周题目,最长回文子串。

    hihocoder和leetcode-leetcode:leetcode

    hihocoder和leetcode leetcode 目录名 功能 Array 数组 Backtracking 回溯 Bit_Manipulation 位操作 Design 数据结构设计 Divide_and_Conquer 分而治之 DP 动态规划 Hash_Table 哈希表 List 链表 Math 数学 Stack 栈...

    hihocoder和leetcode-algoritm-solutions:我在leetcode和其他oj中的算法问题的快速和肮脏的解决方案的

    【标题】"hihocoder和leetcode-algoritm-solutions"是一个综合性的算法解决方案集合,它包含作者在解决在线编程挑战平台hihocoder和LeetCode上的算法问题时所编写的代码。这个项目的目标是提供快速而实用的解题策略...

    hihocoder和leetcode-JInterview:J访谈

    hihocoder和leetcode JInterview 一套完整的Java学习路径帮助自己拿到大厂Offier 目录 在线练习 在线面试编程 操作系统和团队工具 基础深入 框架源码 微服务架构 高并发分布式

    leetcode2-algorithm:这个repo是记录我们所有成员在各个题目网站(leetcode、hihocoder等)做的题目

    这个repo是记录我们所有成员在各个题目网站(leetcode、hihocoder等)做的题目; repo的内容仍需要完善,做题网站也不仅仅限制于已有的这些题目来源。 鉴于这是python社区,所以目前主要支持python3代码(py2不再...

    hihocoder和leetcode-hihoCoder-training:这个存储库是保存我在hihoCoderwebsit中解决问题的代码

    hihocoder和leetcode hihoCoder-training This repository is a place to save the code that I solve problem in hihoCoder websit. 里面的题目来源:hihocoder、编程之美、剑指offer和LeetCode。

    hihocoder和leetcode-OJPractice:OJ实践

    hihocoder和leetcode OJPractice ##文件夹组织方式(暂定): 一级文件夹按照题库组织,即分别建立Hihocoder、Leetcode、POJ等文件夹 二级文件夹命名格式为: 题号_人名ID[_语言] ,如果语言不是C/C++请添加“_语言...

    hihocoder和leetcode-algorithm:做的一些oj题

    hihocoder和leetcode personal algorithm exercise on leetcode, nowcoder and hihocoder 在leetcode, nowcoder和hihocoder网站上做的的算法练习

    hihocoder和leetcode-blog:日志记录

    hihocoder和leetcode 日志记录 线上工具 1.jsLint,jsHint: 2.jsFiddle,jsBin: 3.Dabblet: 4.Compilr:是一个在线编译器和在线IDE。可以用它来开发PHP, C, C++, Ruby。在浏览器中编译Java, C# 和 VB.net等。 5.便捷的...

    hihocoder和leetcode-CodingInterviewsNotes.gi:CodingInterviewsNotes.gi

    hihocoder和leetcode Coding_Interviews_CN_Notes 大体涵盖以下知识 C++ Primer 5th effective C++ STL (api和demos) C++ 基础知识与理论 智能指针、C++11、 Linux命令 Unix操作系统(进程、线程、内存管理、信号) ...

    hihocoder和leetcode-algo_practice:记录算法过程,每天更新!

    hihocoder和leetcode algo_practice record the algorithm process, update every day! // In this reposity, 常考知识点算法: 排序:大部分要求能手写,并分析时间空间复杂度,以及稳定性分析 快速排序,插入排序,...

    hihocoder和leetcode-online-programming-problem:在线编程问题

    hihocoder和leetcode #Online Programming Problem 一些在线编程题目的AC代码和题解 GoogleCode Google Past Contests 的AC代码以及题解 hihoCoder 的AC代码以及题解 LeetCode 的AC代码以及题解 otherCode 一些公司...

    hihocoder和leetcode-aoj-cli:all-online-jugde-commond-line

    hihocoder和leetcode all online judge code cli 各oj的命令行前端... 想法来源: 进展 已支持ctguoj全部功能 hihocoder 支持登录、查看比赛列表,题目列表,显示题目信息 这个无聊的项目先停止了... 使用及开发 git ...

    hihocoder和leetcode-hiho-and-leet:hiho-and-leet

    【标题】"hihocoder和leetcode-hiho-and-leet:hiho-and-leet" 提供的项目,主要关注的是两个知名的在线编程挑战平台——hihocoder和LeetCode。这两个平台都致力于帮助程序员提升编程技能,尤其是对于算法和数据结构...

    hihocoder和leetcode-Algorithm:格物致知!

    hihocoder和leetcode Leetcode 在线平台 Comet OJ 教程 Just Code 针对面试训练算法题, 目前包括字节跳动面试题、 LeetCode 和剑指 offer 写在20年初的校招面试心得与自学CS经验及找工作分享 labuladong的算法小抄 ...

    hihocoder和leetcode-DataStructures-Algorithms:继续编码!

    hihocoder和leetcode 学习数据结构和算法 基础的数据结构/算法 日常练习 ,杭州电子科技大学Online Judge ,北京大学Online Judge ,计蒜客上的题库,有题型分类 ,南阳理工学院Online Judge,有题型分类 比赛 ,...

    online judge源码

    在线评测系统,也被称为Online Judge(OJ),是编程竞赛和教育领域中的一个重要工具,它能够自动评判用户提交的代码是否符合预设的测试用例。... ...1. 用户认证与权限管理:确保只有合法用户可以提交代码,同时控制不同...

    leetcode跳跃-dnight-framework:夜间密码

    dnight-hihocoder hihocoder 刷题 dnight-leetcode leetcode 刷题 10 个数据结构: 数组、链表、栈、队列、散列表、二叉树、堆、跳跃表、图、Trie 树。 10 个算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法...

    leetcode和oj-OJ:来自leetcode、lintcode和hihocode的OJ

    HihoCoder经常举办各类编程竞赛,包括ACM/ICPC风格的比赛,这些比赛不仅考验个人编程技巧,还要求参赛者在有限时间内快速理解问题、设计解决方案。此外,HihoCoder的社区也有丰富的讨论区,方便用户交流解题经验。 ...

Global site tag (gtag.js) - Google Analytics