ACM►刷题实战►hdu

hdu6583

###name
Typewriter

###descirption
One day, Jerry found a strange typewriter. This typewriter has 2 input modes: pay p coins to append an arbitrary single letter to the back, or q coins to copy a substring that has already been outputted and paste it in the back.
Jerry now wants to write a letter to Tom. The letter is a string S which contains only lowercase Latin letters. But as Jerry is not very wealthy, he wants to know the minimum number of coins he needs to write this letter.

###input
This problem contains multiple test cases. Process until the end of file.
For each test case, the first line contains string S $(|S|≤2×10^5,∑|S|≤5×10^6)$, consisting of only lowercase Latin letters. And the second line contains 2 integers p and q $(1≤p,q<2^{31})$.

###output
For each test case, output one line containing the minimum number of coins Jerry needs to pay.

###sample input
abc
1 2
aabaab
2 1

###sample output
3
6

###toturial
这个题目首先dp肯定跑不掉的，我们设dp[i]为构造出前i个字母的代价，我们先来分析dp函数的特点，他具有以下这些性质，
* $1.$ dp单调不减
* $2.$ 复制方案的决策点递增，
这两个性质非常好证明

据此我们就可以直接来dp了
dp[i] <- dp[i-1]
dp[i] <- dp[j] 这里要求j是最小的值使得前缀S[1..j]包含子串S[j+1..i]

第二个转移方程的决策点递增，于是我们就可以直接利用这一点，来使用后缀自动机加速
###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
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
#include<bits/stdc++.h>
using namespace std;

struct SAM{//下标从1开始，0作为保留位，用于做哨兵
    //如果没有特殊要求，尽量选择合适的自动机，要算好内存
    //经过hdu1000测试，10000个map大概是10kb,对于1e6的字符串，不建议使用后缀自动机
    typedef map<int,int>::iterator IT;
    static const int MAXN=2e5+10;
    int cnt,last,par[MAXN<<1],len[MAXN<<1];
//    map<int,int>trans[MAXN<<1];//map用于字符集特别大的时候，注意这里占内存可能会特别大
    int trans[MAXN<<1][26];

    inline int newnode(int parent,int length){
        par[++cnt]=parent;
        len[cnt]=length;
//        trans[cnt].clear();
        for(int i=0;i<26;i++) trans[cnt][i]=-1;
        return cnt;
    }

    void ini(){
        cnt=0;
        last=newnode(0,0);
    }

    void extend(int c){
        int p=last;
        int np=newnode(1,len[last]+1);//新建状态，先让parent指向根（1）
        while(p!=0&&trans[p][c]==-1){//如果没有边，且不为空，根也是要转移的
            trans[p][c]=np;//他们都没有向np转移的边，直接连过去
            p=par[p];//往parent走
        }
        if(p!=0){//如果p==0，直接就结束了，什么都不用做，否则节点p是第一个拥有转移c的状态，他的祖先都有转移c
            int q=trans[p][c];//q是p转移后的状态
            if(len[q]==len[p]+1)par[np]=q;//len[q]是以前的最长串，len[p]+1是合并后的最长串，相等的话，不会影响，直接结束了，
            else{
                int nq=newnode(par[q],len[p]+1);
//                trans[nq]=trans[q];//copy出q来，
                for(int i=0;i<26;i++) trans[nq][i]=trans[q][i];
                par[np]=par[q]=nq;//改变parent树的形态
                while(trans[p][c]==q){//一直往上面走
                    trans[p][c]=nq;//所有向q连边的状态都连向nq
                    p=par[p];
                }
            }
        }
        last=np;//最后的那个节点
    }//SAM到此结束
}sam;


int main(){
    // freopen("/Users/s/Desktop/02in.txt","r",stdin);
//    freopen("/Users/s/Desktop/02out.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s;
    int a,b;
    while(cin>>s>>a>>b){
        vector<int>dp(s.size());
        sam.ini();
        sam.extend(s[0]-'a');
        dp[0]=a;
        int last=1; //rt
        int j=0;// match s[j+1,i]
        for(int i=1;i<s.size();i++){
            //assert(sam.len[sam.par[last]]<=i-1-(j+1)+1);
            while(j<i){
                if(sam.trans[last][s[i]-'a']!=-1) {
                    last=sam.trans[last][s[i]-'a'];
                    break;// find it
                }
                else{//match s[j+1,i-1] and can't match s[j+1,i] -> match s[j+2,i-1]
                    sam.extend(s[++j]-'a');
                    if(last!=1&&sam.len[sam.par[last]]>=(i-1)-(j+1)+1) last=sam.par[last];
                    if(last!=1&&sam.len[sam.par[last]]>=(i-1)-(j+1)+1) last=sam.par[last];
                }//只跳一步是不够的，因为extend的时候可能会让原last多一个父亲,所以要跳两步
            }
            dp[i]=dp[i-1]+a;
            if(j!=i) dp[i]=min(dp[i],dp[j]+b);
        }
        cout<<dp.back()<<endl;
    }
}





/*
 *
 *
 *





baaabbabbbabbaa
1 1



 */







ACM►学习笔记►图论

最大流最小割算法

二分图的最小顶点覆盖

定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。

方法：最小顶点覆盖等于二分图的最大匹配。

我们用二分图来构造最小顶点覆盖。

二分图的最大独立集

定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。

方法：最大独立集=所有顶点数-最小顶点覆盖。

二分图的最大团

定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。

方法：二分图的最大团=补图的最大独立集。

补图的定义是：对于二分图中左边一点x和右边一点y，若x和y之间有边，那么在补图中没有，否则有。

这个方法很好理解，因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。

最小边覆盖

边覆盖集：通俗地讲，所谓边覆盖集，就是G中所有的顶点都是E中某条边的邻接顶点（边覆盖顶点），一条边只能覆盖2个顶点。

注意：在无向图中存在用尽量少的边去“覆盖”住所有的顶点，所以边覆盖集有极小与最小的区别。

极小边覆盖：若边覆盖E中的任何真子集都不是边覆盖集，则称E是极小边覆盖集。

最小边覆盖：边数最小的边覆盖称为最小边覆盖，通俗地讲，就是极小边覆盖中的最小的一个集合。

最小边覆盖 = 最大独立集 = n - 最大匹配

最大权闭合子图

定义：有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。

方法：将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的最小割将图分为两部分,我们发现所有正点权的和减去该简单割便是与s相连的闭合图的权，通过最小割找到了最大权闭合图。

最大密度子图

定义：给定一个无向图，要求它的一个子图，使得子图中边数 与点数 的比值最大，

方法：定义$d_i$为与点i相连的所有边的权值和，定义$p_i$为点i的权，保留以前的图，新建源点s汇点t，s到i连边，权值为U，i到t连边，权值为$2g-d_i-2p_i$

那么$h(g)$的值为$(U\cdot n-maxflow)$，二分答案就行了。

最小路径覆盖子图

定义：对于一个有向图，找出最小的路径条数，使之成为一个路径覆盖．

方法：用原图建立一个两层的新图，如果原图中存在边i->j我们建立的新图就有第一层的点i流到第二层的点j，最后建立超级源点流向 所有的第一层图的点，建立超级汇点，由所有第二层的图流入，用n减去所 求的最大流就是最小路径。

有向无环图最长链、最长反链

在有向无环图中，有如下的一些定义和性质：

链：一条链是一些点的集合，链上任意两个点x, y，满足要么 x 能到达 y ，要么 y 能到达 x 。

反链：一条反链是一些点的集合，链上任意两个点x, y，满足 x 不能到达 y，且 y 也不能到达 x。

一个定理：最长反链长度=最小链覆盖（用最少的链覆盖所有顶点）

对偶定理：最长链长度=最小反链覆盖

最小链覆盖（可以相交的最小路径覆盖）（最长反链长度）（用最少的链覆盖所有顶点）

定义：一条链是一些点的集合，链上任意两个点x, y，满足要么 x 能到达 y ，要么 y 能到达 x 。有向无环图中，找出最小的路径条数，使之成为的一个路径覆盖。

方法：我们将原图做一次Floyd传递闭包，在新图中寻找最小路径覆盖，这样其实就是相当于将原图改造了一下，只要 x 能到达 y ，就直接连一条边 (x, y)，这样就可以“绕过”原图的一些被其他路径占用的点，直接构造新路径了。这样就将可以相交的最小路径覆盖转化为了路径不能相交的最小路径覆盖了。

最大团 = 补图的最大独立集

最小边覆盖 = 二分图最大独立集 = |V| - 最小路径覆盖

最小路径覆盖 = |V| - 最大匹配数

最小顶点覆盖 = 最大匹配数

最小顶点覆盖 + 最大独立数 = |V|

最小割 = 最小点权覆盖集 = 点权和 - 最大点权独立集

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
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=5e4+5,E=5e4+5;
int head[V];
int to[E],nex[E],ew[E],tot=1;
inline void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
void del(int u){repe(i,u) head[u]=0,del(to[i]);}

//最大流最小割算法
int lv[V],current[V],src,dst;
int *cap=ew;//容量等于边权
bool maxflowbfs(){
    queue<int>q;
    lv[src]=0, q.push(src);
    while(!q.empty()){
        int u=q.front();q.pop();
        repe(i,u){
            if(cap[i]==0||lv[to[i]]>=0)continue;
            lv[to[i]]=lv[u]+1, q.push(to[i]);
        }
    }
    return lv[dst]>=0;
}
int maxflowdfs(int u,int f){
    if(u==dst)return f;
    for(int&i=current[u];i;i=nex[i]){//当前弧优化
        if(cap[i]==0||lv[u]>=lv[to[i]])continue;
        int flow=maxflowdfs(to[i],min(f,cap[i]));
        if(flow==0) continue;
        cap[i]-=flow,cap[i^1]+=flow;
        return flow;
    }
    return 0;
}
ll maxflow(int base,int n,int s,int t){
    src=base+s,dst=base+t;
    ll flow=0,f=0;// 计算最大流的过程中不可能爆int 唯独在最后对流量求和对时候可能会比较大 所以只有这里用ll
    while(true){
        rep(i,base+1,base+n) current[i]=head[i],lv[i]=-1;
        if(!maxflowbfs())return flow;
        while(f=maxflowdfs(src,2e9))
            flow+=f;
    }
}
ACM►学习笔记►图论

最短路和第k短路

先bb一堆

dij算法很简单，就是通过不断的松弛离源最近的点，说白了，就是一个bfs变种,或者叫做启发式搜索？启发函数就是当前的距离。搜索过程中松弛点

A*算法也不难，本质上就是启发式搜索，核心就在启发函数f+g上面，其中f为当前走过的路径长度，g为估值函数，估计下还有多远到终点

在一般的A*搜索中，可以解决迷宫问题，用曼哈顿距离来作为g函数，可以跑的飞快

我们可以根据dij算法求出的信息来计算第k短路。

我们对原图的反向图，求出以待求终点为起点的最短路数组，以此作为A*的启发函数的评估函数，可以证明，在此启发函数作为指引的情况下， 我们首先会得到一条从原图起点到终点的路线，如果我们此时不让算法停止，忽略此次结果，那么我们得到的第二个路线是什么呢？

其实就是第二短路。

dijkstra

dijkstra算法，用于解决单源最短路问题，是一种每一次通过贪心的选择距离源点最近的点来松弛其他点来得到解的方法。

为什么选择距离源点最近的没有松弛过其他点的点

在松弛过程中，距离数组（函数）表达的意义是这样的，dist(i)代表到i到最短路不会短于dist(i)

我们尝试用第一数学归纳法来证明松弛的这个点已经达到了最短路状态，

数学归纳法第一步:归纳起点，我们选择松弛的第一个点是源点自己，首先不可否认，对源点自己来说，他已经达到了最短路状态。

数学归纳法第二步:假设我们已经用k个点松弛过其他点，那么这k个点都已经达到了最短路状态，那么我们接下来要选择第k+1个点来松弛其他点， 我们在所有没有松弛过其他点的点中，选出了距离源点最近的点之一，下面来证明这个点已经达到了最短路状态

假设它并非为最短路状态，首先，那就意味着他的最后一步并非通过那k个点到它来得到，肯定是剩余到没有松弛过其点的点得到的， 然鹅，你要到其他点，在到此点，的路，显然比直接到此点更长，因为我们选出的就是离源点最近的点，矛盾。

启发式搜索

对于启发式搜索，他有一个启发函数，看哪个点的启发函数值大/小，就先搜索哪一个，比方说，dfs的启发函数是点的深度，bfs的启发函数是点的深度的相反数。

A*搜索

对于A*搜索，他也有启发函数，他的启发函数一般为当前已经走过的路径长度+评估函数，这个评估函数，在迷宫搜索中一般取曼哈顿距离，在最短路搜索中评估函数一般选取为小于等于真实距离，否则会得到错解，比方说，若把dij算法看着A*搜索，他的的评估函数就是f(x)=0哈哈哈哈。可以证明，评估函数选取为小于等于真实距离， 不会导致算法正确性的改变。

如何求第k短路？

​ 如果我们以每一个点到终点到真实最短距离作为评估函数，这个评估函数简直神了，这不叫评估了，这叫开挂。对我们就是开挂，这个挂好开 建反向图跑dij即可，然后我们以这个启发函数为指引，来搜索，一下子就找到了最短路，0.0 ，这不是我们想要的，丢掉，只要我们不退出程序，我们就会逐渐得到第二短路、第三短路、等等，这个很显然的。

SPFA

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
int d[maxn],inq[maxn];
    void short_path(int s,int*dist){
        for(int i=0;i<=n;i++) dist[i]=1e9;
        dist[s]=0;
        deque<int>q;
        q.push_back(s);
        inq[s]=1;
        long long sum=0;
        while(!q.empty()){
            int u=q.front(); q.pop_front(); sum-=dist[u];inq[u]=0;
            if(1ll*dist[u]*q.size()>sum){//large label last
                sum+=dist[u];
                q.push_back(u);
                inq[u]=1;
            }
            else{
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v, w=edge[i].w;
                    if(dist[v]>dist[u]+w){
                        if(inq[v]){
                            sum-=dist[v];
                            dist[v]=dist[u]+w;
                            sum+=dist[v];
                        }
                        else{
                            dist[v]=dist[u]+w;
                            inq[v]=1;
                            sum+=dist[v];
                            if(dist[v]<dist[q.front()]) q.push_front(v);//small lable first
                            else q.push_back(v);
                        }
                    }
                }
            }
        }
    }

DIJ

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
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=5e4+5,E=5e4+5;
int head[V];
int to[E],nex[E],ew[E],tot=1;
inline void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
void del(int u){repe(i,u) head[u]=0,del(to[i]);}

// dijkstra算法
typedef long long ll;
ll d[V];// 距离数组
typedef pair<ll,int>pii;
void dijkstra(int base,int n,int s,ll*dist){
    rep(i,base+1,base+n) dist[i]=1e18;
    priority_queue<pii,vector<pii>,greater<pii>>q;// dis and vertex
    q.emplace(dist[base+s]=0,base+s);
    while(!q.empty()){
        int u=q.top().second; q.pop();
        repe(i,u){
            int v=to[i],w=ew[i];
            if(dist[u]+w<dist[v])q.emplace(dist[v]=dist[u]+w,v);
        }
    }
}

Astar

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
const int maxn=1e6;
int buf[maxn];
struct graph{
    static const int maxn=1e3+5;
    static const int maxm=1e5+5;
    struct star{
        int v,w,nex;
        star(int v=0,int w=0,int nex=0):v(v),w(w),nex(nex){}
    }edge[maxm];//有向图不要双倍边
    int head[maxn], tot, n;

    void init(int _n){
        n=_n;
        tot=-1;
        memset(head,-1,(n+1)*sizeof(head[0]));
    }

    void add_edge(int u,int v,int w){
        edge[++tot]=star(v,w,head[u]);
        head[u]=tot;
    }


    struct dijnode{
        int d,u;
        bool operator<(const dijnode&rhs)const{return d>rhs.d;}
        dijnode(int d,int u):d(d),u(u){}
    };
    void short_path(int s,int*dist){//short path
        for(int i=0;i<=n;i++) dist[i]=2e9;
        priority_queue<dijnode>q;// dis and vert
        dist[s]=0;
        q.push(dijnode(dist[s],s));
        while(!q.empty()){
            int u = q.top().u; q.pop();
            for(int i=head[u];~i;i=edge[i].nex){
                int v=edge[i].v, w=edge[i].w;
                if(dist[u]+w<dist[v]){
                    dist[v]=dist[u]+w;
                    q.push(dijnode(dist[v],v));
                }
            }
        }
    }


    struct Astarnode{
        int d,need,u;
        bool operator<(const Astarnode&rhs)const{return d+need>rhs.d+rhs.need;}
        Astarnode(int d,int need,int u):d(d),need(need),u(u){}
    };
    int kthway(graph&rev,int s,int t,int k){//from s to t the kth way ， g是反向图
        if(s==t)k++;
        int*dist=buf;//分配内存
        rev.short_path(t,dist);
        if(dist[s]==2e9)return -1;//此路不通
        priority_queue<Astarnode>q;
        q.push(Astarnode(0,dist[s],s));
        while(!q.empty()){
            int u = q.top().u, d=q.top().d;
            q.pop();
            if(u==t){
                k--;
                if(k==0)return d;
            }
            for(int i=head[u];~i;i=edge[i].nex){
                int v=edge[i].v, w=edge[i].w;
                q.push(Astarnode(d+w,dist[v],v));
            }
        }
        return -1;//没那么多路
    }
};
ACM►刷题实战►hdu

hdu6582

###name
Path

###descirption
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.

###input
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers $x,y,c(1≤x,y≤n,1≤c≤10^9)$, denoting that there exists a one-way road from the house indexed x to y of length c.

###output
Print T lines, each line containing a integer, the answer.

###sample input
1
3 4
1 2 1
2 3 1
1 3 2
1 3 3

###sample output
3

###toturial
扣最短路跑最大流即可

###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
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
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=5e4+5,E=5e4+5;
int head[V];
int to[E],nex[E],ew[E],tot=1;
inline void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
void del(int u){repe(i,u) head[u]=0,del(to[i]);}

// dijkstra算法
typedef long long ll;
ll d[V];// 距离数组
typedef pair<ll,int>pii;
void dijkstra(int base,int n,int s,ll*dist){
    rep(i,base+1,base+n) dist[i]=1e18;
    priority_queue<pii,vector<pii>,greater<pii>>q;// dis and vertex
    q.emplace(dist[base+s]=0,base+s);
    while(!q.empty()){
        int u=q.top().second; q.pop();
        repe(i,u){
            int v=to[i],w=ew[i];
            if(dist[u]+w<dist[v])q.emplace(dist[v]=dist[u]+w,v);
        }
    }
}

//最大流最小割算法
int lv[V],current[V],src,dst;
int *cap=ew;//容量等于边权
bool maxflowbfs(){
    queue<int>q;
    lv[src]=0, q.push(src);
    while(!q.empty()){
        int u=q.front();q.pop();
        repe(i,u){
            if(cap[i]==0||lv[to[i]]>=0)continue;
            lv[to[i]]=lv[u]+1, q.push(to[i]);
        }
    }
    return lv[dst]>=0;
}
int maxflowdfs(int u,int f){
    if(u==dst)return f;
    for(int&i=current[u];i;i=nex[i]){//当前弧优化
        if(cap[i]==0||lv[u]>=lv[to[i]])continue;
        int flow=maxflowdfs(to[i],min(f,cap[i]));
        if(flow==0) continue;
        cap[i]-=flow,cap[i^1]+=flow;
        return flow;
    }
    return 0;
}
ll maxflow(int base,int n,int s,int t){
    src=base+s,dst=base+t;
    ll flow=0,f=0;// 计算最大流的过程中不可能爆int 唯独在最后对流量求和对时候可能会比较大 所以只有这里用ll
    while(true){
        rep(i,base+1,base+n) current[i]=head[i],lv[i]=-1;
        if(!maxflowbfs())return flow;
        while(f=maxflowdfs(src,2e9))
            flow+=f;
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n,m;scanf("%d%d",&n,&m);
        struct edge{int u,v,w;};
        vector<edge>e;
        rep(i,1,m) {
            int u,v,w; scanf("%d%d%d",&u,&v,&w);
            addedge1(u,v,w);
            e.push_back(edge{u,v,w});
        }
        dijkstra(0,n,1,d);
        tot=max(tot,tot^1);
        for(edge&x:e) if(d[x.u]+x.w==d[x.v]) {
            addedge1(n+x.u,n+x.v,x.w);
            addedge1(n+x.v,n+x.u,0);
        }
        printf("%lld\n",maxflow(n,n,1,n));
        rep(i,1,2*n) head[i]=0; tot=1;
    }
}
ACM►刷题实战►hdu

hdu6581

###name
Vacation

###descirption
Tom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ith car has a length of $l_i$, the head of it is $s_i$ from the stop-line, and its maximum velocity is $v_i$. The car Tom and Jerry are driving is $l_0$ in length, and $s_0$ from the stop-line, with a maximum velocity of $v_0$.
The traffic light has a very long cycle. You can assume that it is always green light. However, since the road is too narrow, no car can get ahead of other cars. Even if your speed can be greater than the car in front of you, you still can only drive at the same speed as the anterior car. But when not affected by the car ahead, the driver will drive at the maximum speed. You can assume that every driver here is very good at driving, so that the distance of adjacent cars can be kept to be 0.
Though Tom and Jerry know that they can pass the stop-line during green light, they still want to know the minimum time they need to pass the stop-line. We say a car passes the stop-line once the head of the car passes it.
Please notice that even after a car passes the stop-line, it still runs on the road, and cannot be overtaken.

###input
This problem contains multiple test cases.
For each test case, the first line contains an integer n $(1≤n≤10^5,∑n≤2×10^6)$, the number of cars.
The next three lines each contains n+1 integers, $l_i,s_i,v_i (1≤s_i,v_i,l_i≤10^9)$. It’s guaranteed that $s_i≥s_i+1+li+1,∀i∈[0,n−1]$

###output
For each test case, output one line containing the answer. Your answer will be accepted if its absolute or relative error does not exceed $10^{−6}$.
Formally, let your answer be a, and the jury’s answer is b. Your answer is considered correct if $|a−b|max(1,|b|)≤10^{−6}$.
The answer is guaranteed to exist.

###sample input
1
2 2
7 1
2 1
2
1 2 2
10 7 1
6 2 1

###sample output
3.5000000000
5.0000000000

###toturial
我们尝试把位移时间图画出来，发现这是一个凸壳，我们直接暴力维护凸壳即可

###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
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
#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct frac{
    ll x,y;
    frac(ll x_,ll y_){
        ll gcd=__gcd(abs(x_),abs(y_));
        x=x_/gcd;
        y=y_/gcd;
        if(y<0){
            x*=-1;
            y*=-1;
        }
    }
    bool operator>=(const frac&rhs)const{
        ll lcm=y/__gcd(y,rhs.y)*rhs.y;
        return x*(lcm/y)>=rhs.x*(lcm/rhs.y);
    }
};

struct line{ll k,b,h;};

frac getx(line l1,line l2){
    return frac(-(l1.b-l2.b),l1.k-l2.k);
}

double gety(line l1,line l2){
    frac t=getx(l1,l2);
    return double(l1.k)/t.y*t.x+l1.b;
}

int stk[101010];

int main(){
    //freopen("/Users/s/Desktop/02.txt","r",stdin);
    //freopen("/Users/s/Desktop/02out.txt","w",stdout);
    int n;
    while(~scanf("%d",&n)){
        vector<line> l(n+1);
        for(int i=0;i<=n;i++) scanf("%lld",&l[i].h);
        for(int i=0;i<=n;i++) scanf("%lld",&l[i].b),l[i].b*=-1;
        for(int i=0;i<=n;i++) scanf("%lld",&l[i].k);
        stk[0]=0;
        ll d=0;
        for(int i=n;i>=0;i--){
            l[i].b-=d;
            while(stk[0]>=1&&l[stk[stk[0]]].k>=l[i].k) stk[0]--;
            while(stk[0]>=2&&l[stk[stk[0]]].k<l[i].k&& \
                getx(l[i],l[stk[stk[0]]])>=getx(l[stk[stk[0]]],l[stk[stk[0]-1]])) stk[0]--;
            stk[++stk[0]]=i;
            d-=l[i].h;
        }
        d+=l[0].h;
//        cout<<d<<endl;
        for(int i=1;i<=stk[0];i++) l[stk[i]].b+=d;
        while(stk[0]>=2&&gety(l[stk[stk[0]]],l[stk[stk[0]-1]])<=0)stk[0]--;
        line linex{0ll,0ll,0ll};
        frac ans=getx(l[stk[stk[0]]],linex);
        printf("%.12f\n",double(ans.x)/ans.y);
    }
}

/*
 1
 2 2
 14 2
 4 2


 2
2 2 2
100 14 2
1 4 2

 *
 *
 * */
ACM►刷题实战►hdu

hdu6579

###name
Operation

###descirption
There is an integer sequence a of length n and there are two kinds of operations:
0 l r: select some numbers from $a_l…a_r$ so that their xor sum is maximum, and print the maximum value.

1 x: append x to the end of the sequence and let n=n+1.

###input
There are multiple test cases. The first line of input contains an integer T(T≤10), indicating the number of test cases.
For each test case:
The first line contains two integers n,m$(1≤n≤5×10^5,1≤m≤5×10^5)$, the number of integers initially in the sequence and the number of operations.
The second line contains n integers a1,a2,…,an$(0≤a_i\lt 2^{30})$, denoting the initial sequence.
Each of the next m lines contains one of the operations given above.
It’s guaranteed that $∑n≤10^6,∑m≤10^6,0≤x\lt 2^{30}$.
And operations will be encrypted. You need to decode the operations as follows, where lastans denotes the answer to the last type 0 operation and is initially zero:
For every type 0 operation, let $l=(l xor lastans)mod n + 1$, $r=(r xor lastans)mod n + 1$, and then swap(l, r) if $l>r$.
For every type 1 operation, let x=x xor lastans.

###output
For each type 0 operation, please output the maximum xor sum in a single line.

###sample input
1
3 3
0 1 2
0 1 1
1 3
0 3 4

###sample output
1
3

###toturial
我们使用线性基，对每一个前缀都建立一个线性基，贪心的选择考后的向量作为基即可，如此则查询T(30)，添加值T(30)，关键点在于如何通过一个前缀构建另一个前缀的线形基，我们只要保证线形基中的元素有顺序，即某个前缀的基都是相对于这个前缀的后缀最简形式，那么我们就可以在后面进行换基，来构建另一个前缀的基

###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
39
40
41
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)

const int maxn=1e6+6;
int bs[maxn][30],ps[maxn][30];
void add(int n,int x){
    rep(i,0,29) bs[n][i]=bs[n-1][i],ps[n][i]=ps[n-1][i];
    int pos=n;
    per(i,29,0) if(1<<i&x) {
        if(bs[n][i]==0) {
            bs[n][i]=x,ps[n][i]=pos;
            break;
        }
        else {
            if(ps[n][i]<pos)swap(bs[n][i],x),swap(ps[n][i],pos);
            x^=bs[n][i];
        }
    }
}
inline int read(){int x;scanf("%d",&x);return x;}
int main() {
    int t=read();
    while(t--){
        int n=read(),m=read();
        rep(i,1,n) add(i,read());
        int lst=0;
        while(m--){
            if(read()==1) add(++n,read()^lst);
            else{
                int l=(read()^lst)%n+1,r=(read()^lst)%n+1;
                if(l>r)swap(l,r);
                lst=0;
                per(i,29,0) if(ps[r][i]>=l) lst=max(lst,lst^bs[r][i]);
                printf("%d\n",lst);
            }
        }
    }
}
ACM►刷题实战►hdu

hdu6578

###name
Blank

###description
There are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right.
Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is:
There are exactly $x_i$ different numbers among blanks $∈[l_i,r_i]$.
In how many ways can the blanks be filled to satisfy all the conditions? Find the answer modulo 998244353.

###input
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there are two integers n(1≤n≤100) and m(0≤m≤100) in the first line, denoting the number of blanks and the number of conditions.
For the following m lines, each line contains three integers l,r and x, denoting a condition(1≤l≤r≤n, 1≤x≤4).

###output
For each testcase, output a single line containing an integer, denoting the number of ways to paint the blanks satisfying all the conditions modulo 998244353.

###sample input
2
1 0
4 1
1 3 3

###sample output
4
96

###toturial
设dp[a][b][c][d]为填完前d个数之后0，1，2，3最后出现的位置为a,b,c,d且前a个位置都满足题意的方案数，于是我们就可以转移了，注意到0，1，2，3具有轮换对称性，那么dp一定也有他的规律，举个很简单的例子dp[9][3][5][7]和dp[9][7][5][3]一定是相等的，于是我们可以对b,c,d排序来进一步压缩状态，可以提高程序的速度,时间复杂度$n^4$,空间上滚动即可达到$n^3$的复杂度

###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
39
40
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);++i)

const int maxn=103;
int dp[2][maxn][maxn][maxn];
int mx[maxn][5],mi[maxn][5];

const int mod=998244353;
void add(int&a,int&b){a+=b;if(a>=mod) a-=mod;}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,m; scanf("%d%d",&n,&m);
        rep(i,1,n) rep(j,1,4) mx[i][j]=-1e9,mi[i][j]=1e9;
        rep(i,1,m){
            int l,r,x; scanf("%d%d%d",&l,&r,&x);
            mx[r][x]=max(mx[r][x],l);
            mi[r][x]=min(mi[r][x],l);
        }
        rep(i,0,n)rep(j,0,i)rep(k,0,j)dp[1&1][i][j][k]=0;
        dp[1&1][0][0][0]=4;// 因为第一个位置可以填四种数，不妨假设位置0填了所有的数字
        rep(t,1,n){
            rep(i,0,t) rep(j,0,i) rep(k,0,j)dp[(t+1)&1][i][j][k]=0;
            rep(i,0,t-1) rep(j,0,i) rep(k,0,j){
                if(mi[t][1]<=i||mi[t][2]<=j||mi[t][3]<=k||mx[t][2]>i||mx[t][3]>j||mx[t][4]>k) dp[t&1][i][j][k]=0;
                if(dp[t&1][i][j][k]==0) continue;
                add(dp[(t+1)&1][t][i][j],dp[t&1][i][j][k]);
                add(dp[(t+1)&1][t][i][k],dp[t&1][i][j][k]);
                add(dp[(t+1)&1][t][j][k],dp[t&1][i][j][k]);
                add(dp[(t+1)&1][i][j][k],dp[t&1][i][j][k]);
            }
        }
        int ans=0;
        rep(i,0,n-1) rep(j,0,i) rep(k,0,j) add(ans,dp[n&1][i][j][k]);
        printf("%d\n",ans);
    }
}
ACM►学习笔记►图论

支配树 

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=3*1e5+5,E=3*2e5+5;
int head[V],deg[V];
int to[E],nex[E],edge=1;
inline void addedge1(int u,int v) {to[++edge]=v,nex[edge]=head[u],head[u]=edge,deg[v]++;}
void del(int u){repe(i,u) head[u]=0,deg[u]=0,del(to[i]);}

// dominator tree
int dad[V],sdom[V],idom[V],dfn[V],rnk[V],step;
void tarjan(int u,int father){ //if(father==0) step=0;
    dfn[u]=++step,rnk[step]=u,dad[u]=father;
    repe(i,u)if(dfn[to[i]]==0)tarjan(to[i],u);
}
int df[V],dw[V];//dsu
int find(int x){
    if(x==df[x])return x;
    int tmp=find(df[x]);
    if(dfn[sdom[dw[df[x]]]]<dfn[sdom[dw[x]]])dw[x]=dw[df[x]];
    return df[x]=tmp;
}
void Lengauer_Tarjan(int g1,int g2,int n,int s,int g3){// s是起点 g1是正向图,g2是反向图,g3是支配树
    rep(i,g1+1,g1+n) dfn[i]=0;
    step=g1; tarjan(g1+s,0);
    rep(i,g1+1,g1+n) df[i]=i,dw[i]=sdom[i]=i;// init dsu
    per(i,g1+n,g1+2){//以g1为主体，映射其他图
        int u=rnk[i];
        repe(j,u-g1+g2) {// 在g2中枚举反向边
            int v=to[j]-g2+g1;// 映射回g1
            find(v);
            if(dfn[sdom[dw[v]]]<dfn[sdom[u]])sdom[u]=sdom[dw[v]];
        }
        df[u]=dad[u];// 只有后向边产生影响，因为只有后向边的终点满足要求

        addedge1(sdom[u]-g1+g3,u-g1+g3);// g1->g3
        repe(j,dad[u]-g1+g3){//在g3中枚举边
            int v=to[j]-g3+g1; // 映射回g1
            find(v);
            idom[v]=sdom[dw[v]]==dad[u]?dad[u]:dw[v];
        }
    }
    rep(i,g1+2,g1+n) {
        int x=rnk[i];
        if(idom[x]!=sdom[x]) idom[x]=idom[idom[x]];
    }
    del(g3+s);
    rep(i,g1+1,g1+n) addedge1(idom[i]-g1+g3,i-g1+g3);
    rep(i,g1+1,g1+n) cout<<idom[i]<<" "<<sdom[i]<<" "<<i<<endl;
}

//lca
int dep[V],siz[V],son[V],chain[V];//,dad[V],dfn[V];//
void dfs1(int u,int father){//dfs1(1,0)
    dep[u]=dep[father]+1;//ini  because dep[0]=1
    dad[u]=father, siz[u]=1, son[u]=-1;
    repe(i,u){
        int v=to[i];
        dfs1(v,u);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int s){
    dfn[u]=++step;
    chain[u]=s;
    if(son[u]!=-1) dfs2(son[u],s);
    repe(i,u){
        int v=to[i];
        if(v!=son[u]&&v!=dad[u]) dfs2(v,v);
    }
}
int querylca(int x,int y){
    while(chain[x]!=chain[y]){
        if(dep[chain[x]]<dep[chain[y]]) swap(x,y); //dep[chain[x]]>dep[chain[y]]
        x=dad[chain[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);// dep[x]<dep[y]
    return x;
}

inline int read(){int x;scanf("%d",&x);return x;}

int main(){
     freopen("/Users/s/Downloads/2019HDOJ多校3_UESTC/data/1002/1in.txt","r",stdin);
    int t=read();
    while(t--){
        int n=read()+1,m=read();
        int g1=0,g2=n,g3=2*n;  // g1是正向图,g2是反向图,g3是支配树
        rep(i,0,3*n) head[i]=deg[i]=0; edge=1;
        while(m--){
            int u=read(),v=read();
            addedge1(g1+v,g1+u);
            addedge1(g2+u,g2+v);
        }
        rep(i,1,n-1) if(deg[i]==0) addedge1(g1+n,g1+i),addedge1(g2+i,g2+n);
        Lengauer_Tarjan(g1,g2,n,n,g3);
        dfs1(g3+n,0),dfs2(g3+n,g3+n);
        int q=read();
        while(q--){
            int x=g3+read(),y=g3+read();
            printf("%d\n",dep[x]+dep[y]-dep[querylca(x,y)]-1);
        }
        return 0;
    }
}

ACM►刷题实战►hdu

hdu6705

###name
path

###descripption
You have a directed weighted graph with n vertexes and m edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight.

Now there are q queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths.

###input
The input consists of multiple test cases, starting with an integer t (1≤t≤100), denoting the number of the test cases.
The first line of each test case contains three positive integers n,m,q. $(1≤n,m,q≤5∗10^4)$

Each of the next m lines contains three integers ui,vi,wi, indicating that the i−th edge is from ui to vi and weighted wi.$(1≤u_i,v_i≤n,1≤w_i≤10^9)$

Each of the next q lines contains one integer k as mentioned above.$(1≤k≤5∗10^4)$

It’s guaranteed that$ Σn ,Σm, Σq,Σmax(k)≤2.5∗10^5$ and max(k) won’t exceed the number of paths in the graph.

###output
For each query, print one integer indicates the answer in line.

###sample input
1
2 2 2
1 2 1
2 1 2
3
4

###sample output
3
3

###hint
1->2 value :1

2->1 value: 2

1-> 2-> 1 value: 3

2-> 1-> 2 value: 3

###toturial
拓展一条边有两种方式，第一终点往外走 ， 第二相同起点的下一条边，这样做的前提是边要有序，从小到大排好

###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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define per(i,j,k) for(int i=j;i>=(k);--i)
#define repe(i,u) for(int i=head[u];i;i=nex[i])

// graph
const int V=5e4+5,E=5e4+5;
int head[V];
int to[E],nex[E],ew[E],tot=1;
inline void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
void del(int u){repe(i,u) head[u]=0,del(to[i]);}

// kthpath
typedef long long ll;
struct path{
    int u,id;ll d;
    bool operator<(const path&rhs)const{return d>rhs.d;}
};
void kthpath(int l,int r,int k,vector<ll>&dist){ // assert(dist.empty())
    priority_queue<path>q;
    rep(i,l,r) if(head[i]) q.push(path{i,head[i],ew[head[i]]});
    while(k--&&!q.empty()){
        int u=q.top().u,id=q.top().id;
        ll d=q.top().d; q.pop();
        dist.push_back(d);
        if(head[to[id]]) q.push(path{to[id],head[to[id]],d+ew[head[to[id]]]});
        if(nex[id]) q.push(path{u,nex[id],d-ew[id]+ew[nex[id]]});
    }
}

struct edge{ll u,v,w;};

int main() {
    ll T; scanf("%lld",&T);
    while(T--){
        ll n,m,q; scanf("%lld%lld%lld",&n,&m,&q);
        rep(i,1,n) head[i]=0; tot=1;
        vector<edge> vec;
        while(m--){
            ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
            vec.push_back(edge{u,v,w});
        }
        sort(vec.begin(),vec.end(),[](edge&a,edge&b){return a.w>b.w;});
        for(edge e:vec) addedge1(e.u,e.v,e.w);
        vector<ll> ans;
        kthpath(1,n,5e4+5,ans);
        while(q--){
            ll k; scanf("%lld",&k);
            printf("%lld\n",ans[k-1]);
        }
    }
}
ACM►学习笔记►树

树hash 

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
// tree 节点0不准使用
int head[maxn];// point
int to[maxn*2],nex[maxn*2],tot;// edge
inline void _addedge(int u,int v){to[++tot]=v,nex[tot]=head[u],head[u]=tot;}
inline void addedge(int u,int v){_addedge(u,v),_addedge(v,u);}
void deltree(int rt,int father){// deltree() and also don't forget tot
    for(int i=head[rt];i;i=nex[i]) if(to[i]!=father) deltree(to[i],rt);
    head[rt]=0;
}
//  struct tree{int rt,n;}


//tree hash
int pw[maxn*2]={1},hshmod;//pw要两倍
int *hsh,siz[maxn]; //point
int *ehsh; //edge
void dfs(int u,int father){
    siz[u]=1;
    for(int i=head[u];i;i=nex[i]){
        if(to[i]==father)continue;
        dfs(to[i],u), siz[u]+=siz[to[i]];
    }
}
void dfs1(int u,int father){// solve every edge from father->u
    for(int i=head[u];i;i=nex[i]){
        if(to[i]==father) continue;
        dfs1(to[i],u);

        vector<pii>buf;
        for(int j=head[to[i]];j;j=nex[j]){
            if(to[j]==u) continue;
            buf.emplace_back(ehsh[j],2*siz[to[j]]);
        }
        sort(buf.begin(),buf.end());
        ehsh[i]=1;// 左边放1
        for(pii x:buf) ehsh[i]=(1ll*ehsh[i]*pw[x.second]+x.first)%hshmod;
        ehsh[i]=(1ll*ehsh[i]*pw[1]+2)%hshmod;// 右边放2
    }
}
void dfs2(int u,int father,int rt){
    vector<pii>buf;
    for(int i=head[u];i;i=nex[i]) {
        if(to[i]==father) buf.emplace_back(ehsh[i],2*(siz[rt]-siz[u]));
        else buf.emplace_back(ehsh[i],2*siz[to[i]]);
    }
    sort(buf.begin(),buf.end());
    hsh[u]=1;// 左边放1
    for(pii x:buf) hsh[u]=(1ll*hsh[u]*pw[x.second]+x.first)%hshmod;
    hsh[u]=(1ll*hsh[u]*pw[1]+2)%hshmod;// 右边放2

    vector<pii>pre(buf),suf(buf);// 对后面进行处理
    int sz=suf.size();
    for(int i=1,j=sz-2;i<sz;i++,j--){
        pre[i].first=(1ll*pre[i-1].first*pw[pre[i].second]+pre[i].first)%hshmod;// merge i-1 and i
        suf[j].first=(1ll*suf[j].first*pw[suf[j+1].second]+suf[j+1].first)%hshmod;// merge j and j+1
        pre[i].second+=pre[i-1].second;
        suf[j].second+=suf[j+1].second;
    }

    for(int i=head[u];i;i=nex[i]){
        if(father==to[i]) continue;
        ehsh[i^1]=1;//左边放1
        int idx=lower_bound(buf.begin(),buf.end(),pii(ehsh[i],2*siz[to[i]]))-buf.begin();
        if(idx-1>=0) ehsh[i^1]=(1ll*ehsh[i^1]*pw[pre[idx-1].second]+pre[idx-1].first)%hshmod;// 前缀
        if(idx+1<sz) ehsh[i^1]=(1ll*ehsh[i^1]*pw[suf[idx+1].second]+suf[idx+1].first)%hshmod;// 后缀
        ehsh[i^1]=(1ll*ehsh[i^1]*pw[1]+2)%hshmod;//右边放2
        dfs2(to[i],u,rt);
    }
}
void treehash(int u,int*hsh_,int*ehsh_,int base,int hshmod_){//hash all tree of tree u
    hsh=hsh_,ehsh=ehsh_,hshmod=hshmod_;
    dfs(u,0); for(int i=1;i<=siz[u]*2;i++) pw[i]=1ll*pw[i-1]*base%hshmod;
    dfs1(u,0),dfs2(u,0,u);
}
////// end