首页 > 其他分享 >Educational Codeforces Round 162 E 点分治 虚树 树形dp

Educational Codeforces Round 162 E 点分治 虚树 树形dp

时间:2024-03-04 17:59:02浏览次数:34  
标签:Educational 颜色 int 分治 Codeforces Round MAXN 虚树 dp

传送门

给出\(n\le 2\cdot 10^5\)的一棵树,每个节点有一个颜色。

求出路径长度为\(2\)路径首端和尾端拥有相同颜色,且路径上其他点不存在相同颜色的点的路径条数。

当时看错题了,把颜色抽出来后没法做了。

后来感觉能点分治,然后把题看对了,遂写了一个极其抽象的点分治。

除此之外,把某种颜色抽出来后,建立出来虚树,在树上进行简单的\(dp\)即可。

由于虚树大小和每次拿出来的点数同阶,故复杂度是线性的。

除此之外,考虑另一种写法:不用建立虚树直接在树上按照虚树的思想进行dp。

每次只考虑子树内的颜色答案统计。其他颜色不用管,乘上对应组合数即可。

const int MAXN=300010;
int T;
int n,m,len;
int a[MAXN];
ll ans;
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
int c[MAXN];
inline void add(int x,int y)
{
	ver[++len]=y;
	nex[len]=lin[x];
	lin[x]=len;
}
void dp(int x,int fa)
{
    ++c[a[x]];
    int las=c[a[x]];
    go(x)
    {
        if(tn==fa)continue;
        dp(tn,x);
        int w=c[a[x]]-las;
        ans+=w+(ll)w*(w-1)/2;
        c[a[x]]=las;
    }
}
int main()
{
	freopen("1.in","r",stdin);
    sc(T);
    while(T--)
    {
        len=ans=0;
        rep(1,n,i)lin[i]=0,c[i]=0;

        sc(n);
        rep(1,n,i)sc(a[i]);
        rep(2,n,i)
        {
            int x,y;
            sc(x);sc(y);
            add(x,y);add(y,x);
        }
        dp(1,0);
        rep(1,n,i)ans+=(ll)c[i]*(c[i]-1)/2;
        putl(ans);
    }
    return 0;
}

标签:Educational,颜色,int,分治,Codeforces,Round,MAXN,虚树,dp
From: https://www.cnblogs.com/chdy/p/18052302

相关文章

  • Codeforces Round 930 (Div. 1) C dij 建图
    离较好的方法差一点。考虑到了可以按照枚举属性并按照当前属性从小到大排序,这样可以从一个点到大另一个点。设当前在排序序列中点为\(i\)当\(i\)走向\(k,i>=k\)需要支付\(c_k\)的代价。而\(i\)到\(k,i<k\)则需\(k-i+c_k\)的代价。则对于不同的\(i\)由于代价没有连续性,当时想......
  • Codeforces Round 892 (Div. 2)
    \[\large\text{Round7:CodeforcesRound892(Div.2)(VP)}\]一言:所谓人,无论是谁到了最后,都会形单影只。——悠久之翼2最令人无语的是最后三分钟交代码的时候把\(\text{D}\)题交到了\(\text{E}\)题,结果能过的代码直接没有过。。\(\text{D:AndreyandEscapefr......
  • Educational Codeforces Round 120
    \[\large\text{Round1:EducationalCodeforcesRound120(VP)}\]一言:孤独的人不会伤害别人,只会不断地伤害自己罢了。——我的青春恋爱物语果然有问题\(\text{C:SetorDecrease}\)后四题唯一场切题,(别问我为什么只有这一道)。读完题之后,理一下思路,可以很容易的想到......
  • Codeforces Round 893 (Div. 2)
    \[\large\text{Round3:CodeforcesRound893(Div.2)(VP)}\]一言:从你站在桥上看我的那一刻起你就是我的世界——火影忍者不是很满意,还是没有突破\(\text{D}\)题,确实是没有想到这题竟然如此毒瘤。。\(\text{D:TreesandSegments}\)首先不难想到一种思路,就是枚举......
  • Codeforces Round 806 (Div. 4) A-G(补题)
    A.YESorYES?思路:一次判断三个字母是否是y、e、s的大小写即可。这题是很久前写的,哈哈,马蜂改了不少。。#include<bits/stdc++.h>usingnamespacestd;intn;chars[5];intmain(){ scanf("%d",&n); for(inti=1;i<=n;i++){ scanf("%s",s+1); if......
  • 牛客周赛 Round 35
    A.小红的字符串切割思路:拿到了一个长度为偶数的字符串,请你将其切割成长度相等的两部分并输出Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;for(inti=0;i<s.size()/2;i++){cout<<s[i];}c......
  • 牛客周赛 Round 35
    牛客周赛Round35小红的字符串切割代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;typedefdoubledb;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=pair<ll,pair<ll,ll>......
  • 16 Educational Codeforces Round 142 (Rated for Div. 2)C. Min Max Sort(递归、思维
    C.MinMaxSort很不错的一道题目,不过脑电波和出题人每对上,\(qwq。\)正难则反。我们考虑最后一步是怎么操作的。最后一步一定是对\(1\)和\(n\)进行操作那么上一步呢?上一步应该是对\(2\)和\(n-1\)以此类推第一步应该是对\(\frac{n}{2}\)和\(\frac{n}{2}+1\)我们的答案应该......
  • Educational Codeforces Round 143 (Rated for Div. 2)C. Tea Tasting(前缀和+二分、
    C.TeaTasting思路这里枚举有三种思路然后经过考虑3是最可行的,然后接着考虑如何计算贡献这里在实现的时候用了一个差分数组,因为我们需要记录第i个茶师它喝了多少个\(b_i\)以及不满\(b_i\)的用\(c_i\)记录,最后计算一下答案即可。#include<bits/stdc++.h>#defineintlon......
  • Codeforces Round 930 (Div. 2)
    目录写在前面ABCDEF写在最后写在前面比赛地址:https://codeforces.com/contest/1937。被交互杀死的一集。赛时卡C明天有早八就直接睡大觉了,第二天看看D一眼秒了,最困的一集。A签到发现1会被先后交换到2,4,8,16……输出\(2^{\left\lfloor\logn\right\rfloor}\)即可。......