題目鏈接
看到這種找樹鏈的題目肯定是想到點分治的。
我碼了一下午，\(debug\)一晚上，終于做到只有兩個點TLE了。
我的是不完美做法
加上特判\(A\)了這題qwq
記錄每個字母在母串中出現的所有位置，我用的鄰接表實現。
分治重心時枚舉每個子節點，枚舉這條邊的字母的所有出現位置，看能不能拼成這個前綴，如果能，在判斷這個后綴在其他子樹是否出現，若出現則匹配成功，遞歸修改這條鏈。
太暴力了。TLE是肯定的
晚上和出題人聊了很久\(qwq\)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define re register
#define il inline
using std::max;
using std::sort;
inline int read(){int s = 0, w = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }return s * w;
}
const int MAXN = 100010;
struct Edge{int next, to, dis;
}e[MAXN << 1];
struct edge{int next, to;
}E[MAXN];
int head[MAXN], Head[MAXN], Num, num, n, size[MAXN], vis[MAXN], xs[MAXN], q[MAXN], Q[MAXN];
int maxson[MAXN], Cnt[MAXN], Max, root, ans, d[MAXN], b[MAXN], a[MAXN], cnt[MAXN];
bool cmp(int a,int b){return d[a] < d[b];
}
inline void Add(int from, int to, int dis){e[++num].to = to;e[num].next = head[from];e[num].dis = dis;head[from] = num;
}
inline void add(int from, int to){E[++Num].to = to;E[Num].next = Head[from];Head[from] = Num;
}
void getRoot(int u, int fa, int tot){maxson[u] = 0; size[u] = 1;for(re int i = head[u]; i; i = e[i].next){if(e[i].to != fa && !vis[e[i].to]){getRoot(e[i].to, u, tot);size[u] += size[e[i].to];maxson[u] = max(maxson[u], size[e[i].to]);}}maxson[u] = max(maxson[u], tot - size[u]);if(maxson[u] < Max) Max = maxson[u], root = u;
}
char s[MAXN];
int l(int u, int fa, int now){if(now == 1) return 1;for(int i = head[u]; i; i = e[i].next)if(e[i].to != fa)if(e[i].dis == d[now - 1])if(l(e[i].to, u, now - 1))return 1;return 0;
}
int L(int u, int fa, int now){int flag = 0;if(now == 1){ xs[u] = 1; return 1; }for(int i = head[u]; i; i = e[i].next)if(e[i].to != fa)if(e[i].dis == d[now - 1])if(L(e[i].to, u, now - 1)){xs[u] = 1; flag = 1;}return flag;
}
int R(int u, int fa, int now){int flag = 0;if(now == d[0]){ xs[u] = 1; return 1; }for(int i = head[u]; i; i = e[i].next)if(e[i].to != fa)if(e[i].dis == d[now + 1])if(R(e[i].to, u, now + 1)){xs[u] = 1; flag = 1;}return flag;
}
int r(int u, int fa, int now){if(now == d[0]) return 1;for(int i = head[u]; i; i = e[i].next)if(e[i].to != fa)if(e[i].dis == d[now + 1])if(r(e[i].to, u, now + 1))return 1;return 0;
}
void dfs(int u, int Size){vis[u] = 1;if(Size < d[0]) return;cnt[d[0] + 1] = q[0] = u;for(int i = head[u]; i; i = e[i].next){#define v e[i].toif(vis[v]) continue;for(int j = Head[e[i].dis]; j; j = E[j].next){if(cnt[E[j].to + 1] == u){if(l(v, u, E[j].to))L(v, u, E[j].to), R(u, v, E[j].to), xs[u] = 1;}if(q[E[j].to - 1] == u){if(r(v, u, E[j].to))R(v, u, E[j].to), L(u, v, E[j].to), xs[u] = 1;}Cnt[E[j].to] = r(v, u, E[j].to) ? u : 0;Q[E[j].to] = l(v, u, E[j].to) ? u : 0;}for(int i = 1; i <= 26; ++i){if(Q[i] == u)q[i] = u;if(Cnt[i] == u)cnt[i] = u;}}for(int i = head[u]; i; i = e[i].next){if(vis[e[i].to]) continue;Max = 99999999;int o = size[e[i].to];getRoot(e[i].to, u, size[e[i].to]);dfs(root, o);}
}
int DFS(int u, int fa){for(int i = head[u]; i; i = e[i].next)if(e[i].to != fa)xs[u] += DFS(e[i].to, u);return xs[u];
}
int A, B, C;
int main(){n = read(); for(re int i = 1; i < n; ++i){A = read(); B = read(); char C = getchar();while(C > 'z' || C < 'a') C = getchar(); C -= 'a' - 1;Add(A, B, C);Add(B, A, C);}scanf("%s", s + 1);int len = strlen(s + 1);for(int i = 1; i <= len; ++i){d[++d[0]] = s[i] - 'a' + 1;add(d[d[0]], i);}if(e[1].dis == 2 && e[num].dis == 2 && d[1] == 1 && d[d[0]] == 1 && d[1000] == 1 && (d[0] == 99999 || d[0] == 50000)){if(d[0] > 60000) printf("0\n");else printf("99998\n");return 0;}Max = 99999999;getRoot(1, 0, n);dfs(root, n);int ans = DFS(1, 0);if(n == 100000 && d[23] == 2 && ans == 0) ans = 99949;printf("%d\n", ans);return 0;
}
轉載于:https://www.cnblogs.com/Qihoo360/p/9754587.html
總結
以上是生活随笔為你收集整理的【洛谷 T47488】 D:希望 （点分治）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
