ｍｊｔ树

(mjt树)

题目背景

从前森林里有一棵很大的(mjt)树，树上有很多小动物。

题目描述

mjt树上有 (n) 个房间，第 i 个房间住着(a_i) 只第bi 种小动物。
这(n)个房间用(n-1)条路连接起来，其中房间1位(mjt)树的根。
现在每个房间(x)的小动物想知道，以房间x为根的(mjt)树中有多少只它们的同类.

输入输出格式

输入格式：

第一行一个整数n，表示房间数
接下来(n)行，每行两个整数(a_i,b_i)。
再之后(n-1)行，每行两个整数(x,y)，表示x和y之间有一条路径

输出格式：

一行n个数，第(i)个数表示以房间i为根的(mjt)树中(b_i)种小动物有多少只，两个数之间用空格隔开

输入输出样例

输入样例#1：

5
2 1
3 1
4 2
5 1
6 2
1 2
1 3
3 4
3 5

输出样例#1：

10 3 10 5 6

说明

(b_ileq nleq 100000,a_ileq 1000)
by xjjppm.

这个题好像是“理责慨”理叔出的
但是为什么叫“焖箭筒”树我还真不知道

我YY了三个做法
有两种做法能A这道题
首先题目将所有点划分成许多种类
所以我用颜色代替

做法1：

DFS中找到每个点所有的与其颜色相同的所有祖先
在祖先中加上这个点的权值
缺陷：太慢

做法2：

将每个点的权值加到其最近的祖先处
然后在回溯的时候就会逐步加到其所有祖先处
查询很快
如果整棵树是比较均衡的树
那么速度就会还不错
缺陷：很容易被卡

做法3：

在DFS的时候处理正在遍历的链上的所有颜色的节点
这样就可以O(1)找出其最近祖先
同样是将权值加到最近祖先处
速度和DFS遍历树的速度差不多
能非常快速的通过该题

做法1

#include<iostream>
#include<cstdio>
#define N 1000005
using namespace std;

struct node{
    int next,v;
}edge[N];
int head[N],sum;

void add(int a,int b){
    edge[++sum].v=b;
    edge[sum].next=head[a];
    head[a]=sum;
    edge[++sum].v=a;
    edge[sum].next=head[b];
    head[b]=sum;
}

int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];

int find(int s){
    int father=fa[s];
    while(father){
        ans[father]+=(zhong[s]==zhong[father])*duosh[s];
        father=fa[father];
    }
    ans[s]+=duosh[s];
}

void DFS(int s,int fath){
    fa[s]=fath;find(s);
    for(int i=head[s];i;i=edge[i].next){
        if(edge[i].v==fa[s])continue;
        DFS(edge[i].v,s);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        scanf("%d%d",&duosh[i],&zhong[i]);
    for(int i=1;i<n;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    DFS(1,0);
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<' ';
    return 0;
}

做法2

#include<iostream>
#include<cstdio>
#define N 200010
using namespace std;

struct node{
    int next,v;
}edge[N];
int head[N],sum;

void add(int a,int b){
    edge[++sum].v=b;
    edge[sum].next=head[a];
    head[a]=sum;
    edge[++sum].v=a;
    edge[sum].next=head[b];
    head[b]=sum;
}

int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];

int find(int s){
    int father=fa[s];
    while(father){
        if(zhong[s]==zhong[father]){
            ans[father]+=ans[s];
            return 0;
        }
        father=fa[father];
    }
}

void DFS(int s,int fath){
    fa[s]=fath;
    for(int i=head[s];i;i=edge[i].next){
        if(edge[i].v==fa[s])continue;
        DFS(edge[i].v,s);
    }
    find(s);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&duosh[i],&zhong[i]);
    for(int i=1;i<n;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;++i)
        ans[i]=duosh[i];
    DFS(1,0);
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}

做法3

#include<iostream>
#include<cstdio>
#define N 1000010
using namespace std;

struct node{
    int next,v;
}edge[N];
int head[N],sum;

void add(int a,int b){
    edge[++sum].v=b;
    edge[sum].next=head[a];
    head[a]=sum;
    edge[++sum].v=a;
    edge[sum].next=head[b];
    head[b]=sum;
}

int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];

int ff[N];//颜色为i的点最后一次出现的位置 
int color[N];

void DFS(int s,int fath){
    fa[s]=fath;
    int fn=ff[zhong[s]];
    ff[zhong[s]]=s;
    for(int i=head[s];i;i=edge[i].next){
        if(edge[i].v==fa[s])continue;
        DFS(edge[i].v,s);
    }
    ans[fn]+=ans[s];
    ff[zhong[s]]=fn;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&duosh[i],&zhong[i]);
    for(int i=1;i<n;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;++i)
        ans[i]=duosh[i];
    DFS(1,0);
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}

ｍｊｔ 树