Post 2019.5.12

Veröffentlicht am | Edited on

我们必须抱有希望，这并不是因为希望真的存在，而是因为我们要做高贵的人。

【模板】树上前缀排序（雾）

题目描述

给定一颗以 $1$ 为根包含 $n$ 个节点的树，保证对于 $2$ ~ $n$ 的每个节点，其父亲的编号均小于自己的编号。
每个节点上有一个的字符，一个节点所代表的字符串定义为从根节点到这个节点的简单路径上经过的所有字符连起来形成的字符串。
请你给这些字符串按照字典序排序。
特别地，如果两个节点所代表的字符串完全相同，它们的大小由它们的父亲所代表的字符串的大小决定，如果仍相同，则由它们编号的大小决定。

输入输出格式

输入格式：
第 $1$ 行包含一个正整数 $n$。
第 $2$ 行包含 $n-1$ 个数 $f_{2 \dots n}$，其中 $f_i$ 表示 $i$ 的父亲。
第 $3$ 行为一个包含 $n$ 个小写字母的字符串 $s$，其中 $s_i$ 表示编号为 $i$ 的节点上的字符。
输出格式：
输出一行 $n$ 个正整数，第 $i$ 个正整数表示代表排名第 $i$ 的字符串的节点编号。
输入输出样例

输入样例#1：
5
1 1 3 2
abbaa

输出样例#1：
1 5 4 2 3

说明

对于 $20\%$ 的数据，$1 \le n \le 10 ^ 3$。
对于 $50\%$ 的数据，$1 \le n \le 10 ^ 5$。
对于 $100\%$ 的数据，$1 \le n \le 5 \times 10 ^ 5$。

题解

I may have a $O(n)$ ideal….

The set of character is really small

Firstly , if we have a trie , we could sort all the paths which are from the node to the root by DFS in $O(n)$ time.

So how could we get the tree ?

find every point’s father is given by the order of the number , the char of root is meaningless to the other paths….So we let the edge to the father own the char.

Each Node has a vector to save numbers , and a a array size of 26 to $O(1)$ check if the father has the $c_i$ or transfer to $c_i$

suppose the current point is $i$ , the char is $c_i$ , the father is $f_i$ , we use a array size of 26 to $O(1)$ check if the father has the $c_i$ , if the father has the $c_i$ , we push the number to the vector of the Node…

The correctness of this is same as the normal tree proof:

when father is the root , it’s apparently right .

else

if the node p , q have same char from the the father , we merge it..

consider the subtree.

let s is p’s son , t is q’s son , if $c(s) = c(t)$ , the situation of two node is right , the correctness is depend on sons.

if $c(s) \ne c(t) $ , it is ordinary situation , which depend on the correctness of father..

we used inductive method.

Emmmm , could you understand the proof above ?

Or we could prove the each path on given tree , has the only path on the tree we create.

So the complexity is $O(n)$ , code will be finished tomorrow because Toto ask me some inclusion-exclusion principle problems….

Writing the code…..

草我又发现我读错题了。我这实在堪忧。错误的题意：从根到节点，正确的是：节点到根。

错误题意的代码（也许可以出一道联赛模拟题？）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
const int maxn = (int)5e5;
int c[26][maxn] , f[maxn] , fn[maxn] , rev[maxn] , n , tot = 1;
std::vector<int> b[maxn] ;
// f is the given father , fn is the new tree father of node , rev is the map of point to map

inline void ins(int x , int ch)
{
	if(c[ch][rev[f[x]]]) rev[x] = c[ch][rev[f[x]]];
	else rev[x] = c[ch][rev[f[x]]] = ++tot;
	b[rev[x]].push_back(x);
}
void DFS(int x)
{
	for(int i = 0 ; i < (int)b[rev[x]].size() ; ++i)
		printf("%d ",b[rev[x]][i]);
	for(int i = 0 ; i < 26 ; ++i)
		if(c[i][rev[x]])
			DFS(c[i][rev[x]]);
}
char s[maxn];
int main()
{
	scanf("%d",&n);
	for(int i = 2 ; i <= n ; ++i)
		scanf("%d",&f[i]);
	f[1] = 1;
	scanf("\n%s",s+1);
	for(int i = 1 ; i <= n ; ++i)
		ins(i , (int)s[i] - 97);
	for(int i = 1 ; i <= tot ; ++i)
		std::sort(b[i].begin() , b[i].end());
	DFS(1);
}

其实这个错误的题意还是很有意思的。

真模板好像就是广义SAM了吧，插入特殊字符然后分配所有后缀标记然后DFS一遍就是线性的？

树上游戏

每个节点有一个颜色，定义$s(i,j)$表示$i$到$j$的颜色数。

求出对于每个$i$ , $\sum\limits_{j=1}^{n}s(i,j)$

题解

先来个$O(n^2)$暴力看看有没有读错题（怕了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
const int maxn = (int)1e5;
int ct , n , c[maxn] , s[maxn] , head[maxn];
long long sum[maxn];
struct edge{
	int next , to;
}e[maxn<<1];

inline void add(int x , int y)
{
	e[++ct] = (edge){head[x] ,  y};
	head[x] = ct;
}

void calc(int x , int f , int cur , int src)
{
	sum[src] += cur;
	for(int i = head[x] ; i ; i = e[i].next)
	{
		if(e[i].to == f) continue;
		s[c[e[i].to]] ++ ;
		calc(e[i].to , x , cur + (s[c[e[i].to]] == 1) , src);
		s[c[e[i].to]]--;
	}
}

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&c[i]);
	for(int i = 1 ; i < n ; ++i)
	{
		int x, y;
		scanf("%d%d",&x,&y);
		add(x,y) , add(y,x);
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		s[c[i]] ++ ;
		calc(i , i , 1 , i);
		s[c[i]]--;
	}
	for(int i = 1 ; i <= n ; ++i)
		printf("%lld\n",sum[i]);
}

40pts到手（打爆力明题意）

点分正解？

考虑点分治，对于当前分治中心，统计出它自己出发到分治块内的所有路径对自己答案的贡献，和经过它的路径对当前分治块内点的贡献。自己出发到分治块内的所有路径对自己答案的贡献很好求，现在考虑怎么求经过它的路径对当前分治块内点的贡献。
我们对于当前分治中心的每一个子树分别考虑，令$cnt[i]$为从分治中心出发的进入其他子树的所有路径中，包含颜色$i$的路径条数，$size$为除了该子树外当前分治块内所有的点的个数。那么，我们dfs这棵子树计算贡献，假设当前dfs到$x$，首先给$sum_x$加上$\sum cnt[i]$，即所有在其他子树中出现的颜色的贡献总和，然后计算$x$到分治中心的路径上颜色的贡献。
对于一个出现在分治中心到$x$的路径上的颜色$c$，它对$x$的贡献为$size-cnt[c]$，因为$c$已经在一些路径上出现，它现在能产生的额外贡献为它原来没有出现的路径条数。所以我们给$sum_x$还要加上$size-cnt[c]$。同时$c$也会对$x$的子树内所有点产生贡献，所以这个贡献要像标记一样往下传递，然后标记一下$c$的贡献已经被计算过，往下dfs时就不用再次计算了。
所以只需要对于当前分治中心求出$cnt$数组和每棵子树的$size$，进入一棵子树时减去子树自己内部对$cnt$产生的贡献。同时为了防止复杂度退化，我们不能对于所有颜色求$cnt$，要先统计一下当前分治块内有哪些颜色出现了，这样枚举块内所有颜色的复杂度才是O(分治块大小)。

复杂度$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
    T f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x*=f;
}

typedef long long LL;
const int maxn=100010,inf=0x7fffffff;
struct edge{
    int to,nxt;
}e[maxn<<1];
int n,num,head[maxn],c[maxn];
int f[maxn],size[maxn],Size,root;
int has[maxn],col[maxn],top,cl[maxn],tp;
LL sum[maxn],res[maxn],cnt[maxn],ct[maxn],cct[maxn],path,tot;
bool vis[maxn],exist[maxn];

void addedge(int,int);
void get_sum(int,int);//计算子树大小
void get_root(int,int);//计算重心
void Dfs(int,int,LL*);//统计哪些颜色出现过，同时计算cnt数组
void Modify(int,int,LL);//更新子树的答案
void Calc(int);//对于分治中心统计答案
void Solve(int);//点分治

int main(){
    read(n);
    For(i,1,n) read(c[i]);
    For(i,1,n-1){
        int u,v;
        read(u);read(v);
        addedge(u,v);
    }
    Solve(1);
    For(i,1,n) printf("%lld\n",sum[i]);
    return 0;
}

void Calc(int x){
    get_sum(x,Size=0);

    tot=top=0;
    Dfs(x,0,cnt);
    For(i,1,top) exist[col[i]]=false;//要及时还原标记数组
    For(i,1,tp=top){
        tot+=cnt[cl[i]=col[i]];
        cct[col[i]]=cnt[col[i]];
    }

    sum[x]+=tot;
    LL temp=tot;

    for(int i=head[x];i;i=e[i].nxt) if(!vis[e[i].to]){

        has[c[x]]=1;top=0;
        Dfs(e[i].to,x,ct);
        has[c[x]]=0;
        For(j,1,top) exist[col[j]]=false;

        cnt[c[x]]-=size[e[i].to];
        tot-=size[e[i].to];
        For(j,1,top){
            cnt[col[j]]-=ct[col[j]];
            tot-=ct[col[j]];
        }

        path=size[x]-size[e[i].to];
        Modify(e[i].to,x,0);

        cnt[c[x]]+=size[e[i].to];
        tot=temp;
        For(j,1,top){
            cnt[col[j]]=cct[col[j]];
            ct[col[j]]=0;
        }
    }

    For(i,1,tp) cnt[cl[i]]=0;//还原数组
    vis[x]=true;
}
void Modify(int x,int fa,LL lst){//lst为之前下传下来的贡献和
    LL tag=lst;
    if(++has[c[x]]==1) tag+=path-cnt[c[x]];
    sum[x]+=tot+tag;
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to==fa||vis[e[i].to]) continue;
        Modify(e[i].to,x,tag);
    }
    has[c[x]]--;
}
void Dfs(int x,int fa,LL *cnt){
    if(!exist[c[x]]) col[++top]=c[x],exist[c[x]]=true;
    if(++has[c[x]]==1) cnt[c[x]]+=size[x];
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to==fa||vis[e[i].to]) continue;
        Dfs(e[i].to,x,cnt);
    }
    has[c[x]]--;
}
void Solve(int x){
    Calc(x);
    for(int i=head[x];i;i=e[i].nxt) if(!vis[e[i].to]){
        f[Size=root=0]=inf;
        get_sum(e[i].to,x);
        get_root(e[i].to,x);
        Solve(root);
    }
}
void get_sum(int x,int fa){
    Size++;size[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to==fa||vis[e[i].to]) continue;
        get_sum(e[i].to,x);
        size[x]+=size[e[i].to];
    }
}
void get_root(int x,int fa){
    f[x]=0;
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to==fa||vis[e[i].to]) continue;
        get_root(e[i].to,x);
        chkmax(f[x],size[e[i].to]);
    }
    chkmax(f[x],Size-size[x]);
    if(f[x]<f[root]) root=x;
}
void addedge(int u,int v){
    e[++num].to=v;e[num].nxt=head[u];head[u]=num;
    e[++num].to=u;e[num].nxt=head[v];head[v]=num;
}

溜了溜了