个人域名备案网站内容怎么写,互联网的营销推广方式,亚当学院网站建设视频教程,实时网站制作正题
题目链接:https://www.luogu.com.cn/problem/P3346 题目大意
一棵树#xff0c;求树上所有路径构成的字符串有多少种。#xff08;叶子不超过303030个#xff09; 解题思路
如果是根节点到一些节点的路径的话很好做#xff0c;直接建广义SAMSAMSAM即可#xff0c;…正题
题目链接:https://www.luogu.com.cn/problem/P3346 题目大意
一棵树求树上所有路径构成的字符串有多少种。叶子不超过303030个 解题思路
如果是根节点到一些节点的路径的话很好做直接建广义SAMSAMSAM即可但是因为路径会拐弯所以我们考虑如何统计拐弯的路径。
不难发现如果选择另一个叶子作为根那么就能让某些拐弯的路径变直在每个叶子节点处都跑一遍建立广义SAMSAMSAM即可。
时间复杂度O(30n)O(30n)O(30n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,M3e610;;
struct node{ll to,next;
}a[N*2];
ll n,m,tot,ans,w[N],ls[N],in[N];
ll cnt,len[M],fa[M],ch[M][10];
ll Ins(ll c,ll p){if(ch[p][c]){ll qch[p][c];if(len[p]1len[q])return q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;return nq;}}ll npcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[np]fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;in[y];return;
}
void dfs(ll x,ll fa,ll last){ll tmpIns(w[x],last);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x,tmp);}return;
}
int main()
{scanf(%lld%lld,n,m);cnt1;for(ll i1;in;i)scanf(%lld,w[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}for(ll i1;in;i)if(in[i]1)dfs(i,0,1);for(ll i1;icnt;i)anslen[i]-len[fa[i]];printf(%lld,ans);
}
