T14212 烟花-题解

· · 个人记录

本题是树上的修改。修改次数m较大。

方法一：离线统计

每次修改，修改自己和关联节点。 每次统计能观看到烟花的素数加入计数。如果u节点观看次数为cnt,那么这个节点对答案的贡献为\sum_{i=1}^{cnt}i=cnt*(cnt+1)/2.

现在只需要统计每个节点的观看次数。用一个桶来统计节点的燃放次数。o(m)离线后，遍历每个节点，统计节点及其关联节点的观看次数。

时间复杂度 o(m+n).

#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
const int N = 100005;
int n,m,cnt[N]; ll num[N],ans;
struct Edge{ int to,nxt; }e[N<<1]; int head[N], ec;
void add(int a,int b){ e[++ec].to=b; e[ec].nxt=head[a]; head[a]=ec; }

int main(){
    read(n); read(m); int x;
    for(int i=2;i<=n;i++){
        read(x); add(x,i); add(i,x);
    }
    for(int i=1;i<=m;i++){
        read(x); cnt[x]++;//离线对节点x的修改次数
    }
    for(int u=1;u<=n;u++){
        num[u]+=cnt[u];//他自己燃放观看烟花的次数
        for(int i=head[u];i;i=e[i].nxt){//他作为观众观看燃放烟花的次数
            num[e[i].to]+=cnt[u];
        }
    }
    for(int i=1;i<=n;i++){//离线统计总次数。
        ans+=num[i]*(num[i]+1)/2;
    }
    printf("%lld\n",ans);
}

方法二 在线统计

每次修改一个点时，会被更新的是它自己、它父亲、它儿子，如果我们用一个数组来存每个点周围的个点的和，那么一个点的修改造成影响的除了自己、父亲、儿子之外还有“祖父”，“孙子”，“兄弟”——对于它自己，修改了多少个点就需要加几；对于父亲和儿子，相邻点权值和+2；对于祖父、孙子、兄弟，相邻点权值和+1。

对每个点维护三个标记：

f1[x] 点x自己+1的次数

f2[x] x的儿子+1的次数

f3[x] x的孙子+1的次数

显然每次修改x之后总数为：

父亲节点fa[x]的值为：它自己加一次数+它儿子加一的次数+它的父亲加一的次数。

它自己x的值：它自己加一次数+它儿子加一的次数+它的父亲加一的次数。

它孩子yi的贡献：孩子个数*它加一的次数+它儿子加一的次数+它孙子+1的次数。

我们在每次修改的时候网上维护到“祖父”即可把f1,f2,f3维护出来。


#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1e5+10, M = 1e7+10,mod = 19260817;
int n,m;
ll ans = 0;
int f1[N],f2[N],f3[N],child[N],fa[N];
void update(int x){
    f1[x]++;
    if(x!=1) f2[fa[x]]++;
    if(fa[x]!=1) f3[fa[fa[x]]]++;
}
ll cal(int x){
    ll ans1 = 0;
    ans1 += (ll)f1[x] + f1[fa[x]] + f2[x];
    ans1 += (ll)f1[fa[x]]+f2[fa[x]]+f1[fa[fa[x]]];
    ans1 += (ll)f1[x]*child[x] + f2[x] +f3[x];
    return ans1;
} 
int main(){
    scanf("%d %d",&n,&m);
    int u;
    for(int i=1;i<=n-1;i++){
        scanf("%d",&u);
        fa[i+1] = u;
        child[u]++;
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&u);
        update(u);
        ll res = cal(u);
        ans = (ans+ res) ;
    }
    cout<<ans;
    return 0;
}