## 【Codeforces 715C】Digit Tree

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000 + 9;

int n,MOD; LL vout;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;

void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}

void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}

void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}

void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}

inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 2342】[Shoi2011] 双倍回文

manacher自己做的第一题！ 2A！ 撒花！ *★,°*:.☆\(￣▽￣)/$:*.°★* 最开始看这个题：树套树？二维偏序的既视感……然而树套树求取区间最值的空间复杂度绝对过不了 于是可耻看题解，瞄了一眼：用set就可以水掉QAQ 于是再自己推一推，确定两个set连起来就可以搞 搞一搞520ms水过去了 再一看题解，还可以只用一个set水过去QAQ 不过跑出来反而比hzwer的一个set快一点…….. #include<iostream> #include<cstdio> #include<cstring> #include<set> using namespace std; const int MAXN = 1200000; char pat[MAXN],BUF[MAXN]; int p[MAXN],rt,n,len,vout; inline void manacher(){ len = n*2+1; for (int i=1,p1,p2;i<=len;i++){ if (p[rt]+rt > i) p[i] = min(p[rt*2-i],p[rt]+rt-i); else p[i] = 0; p1 = i+p[i]; p2 = i-p[i]; while (pat[++p1] == pat[--p2]) p[i]++; if (pat[rt]+rt < p[i]+i) rt = i; } } inline void init(){ scanf("%d%s",&n,BUF+1); for (int i=1;i<=n;i++){ pat[i*2-1] = '@'; pat[i*2] = BUF[i]; } pat[n*2+1] = '@'; pat[0] = '#'; pat[n*2+2] = '$';
}

struct cmp{
bool operator () (const int &a, const int &b){
return a+p[a] < b+p[b];
}
};

set<int> por;
set<int,cmp> list;
set<int>::iterator itr;
set<int,cmp>::iterator ITR;
pair<set<int,cmp>::iterator,bool> TMP;

inline void solve(){
for (int i=3;i<=len;i+=2){
int p1 = i-p[i]/2,buf=0;
itr = por.lower_bound(p1);
if (itr != por.end()){
buf = (i-*itr+1)/2;
vout = max(vout, buf*4);
}

TMP = list.insert(i);
if (TMP.second) por.insert(i);

ITR = list.begin();
while (!list.empty() && *ITR+p[*ITR] < i+2)
por.erase(*ITR), list.erase(ITR),ITR = list.begin();
}
printf("%d",vout);
}

int main(){
init();
manacher();
solve();
return 0;
}


## 【Tricks】STL容器使用指南

1.set.insert() 的返回值是 pair;, 其中bool表示是否插入成功
2.set/map当中的earse() 是完全没有检查机制的（我TM都比他写得好！），使用的时候一定要小心
3.set/map/priority_queue可以仅重载其中的比较符号，例如：

struct CMP{
bool operator () (const int &a, const int &b){
return a < b;
}
};

set<int,CMP> S;
map<int,int,CMP> M;
priority_queue<int,vector<int>,CMP> Q;


4.map使用[]进行访问的时候，即使仅仅是查询、不是赋值，map仍然会新建一个节点
5.sort排序传进去的尾地址不会参与排序