結果

問題 No.2360 Path to Integer
ユーザー 👑 potato167potato167
提出日時 2023-06-23 21:48:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 155 ms / 2,500 ms
コード長 4,357 bytes
コンパイル時間 2,756 ms
コンパイル使用メモリ 222,396 KB
実行使用メモリ 44,216 KB
最終ジャッジ日時 2023-09-13 16:48:50
合計ジャッジ時間 5,014 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 10 ms
5,104 KB
testcase_09 AC 152 ms
22,452 KB
testcase_10 AC 87 ms
22,352 KB
testcase_11 AC 91 ms
22,276 KB
testcase_12 AC 83 ms
22,372 KB
testcase_13 AC 155 ms
21,984 KB
testcase_14 AC 154 ms
40,160 KB
testcase_15 AC 152 ms
22,372 KB
testcase_16 AC 154 ms
44,216 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using std::cout;
using std::cin;
using std::endl;
using ll=long long;
using ld=long double;
ll ILL=2167167167167167167;
const int INF=2100000000;
const int mod=998244353;
#define rep(i,a,b) for (ll i=a;i<b;i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";}
template<class T> void vec_out(vector<T> &p){for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){assert(!a.empty());T ans=a[0]-a[0];for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}


//https://trap.jp/post/1702/
template<class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
struct RerootingDP {
    struct edge{
        int from, to, idx, rev_idx;
    };
    RerootingDP (int _n = 0) : n(_n) { es.resize(n);}
    void add_edge(int u, int v, int idx1, int idx2){
        es[u].push_back({u,v,idx1,idx2});
        es[v].push_back({v,u,idx2,idx1});
    }
    V build(int v = 0){
        root = v;
        vis.resize(n,0);
        outs.resize(n);
        return dfs(root);
    }
    vector<V> reroot(){
        reverse_edge.resize(n);
        reverse_edge[root] = e();
        answers.resize(n);
        bfs(root);
        return answers;
    }
  private:
    int n, root;
    vector<vector<edge>> es;
    vector<int> vis;
    vector<vector<E>> outs;
    vector<E> reverse_edge;
    vector<V> answers;
    V dfs(int v){
        vis[v]++;
        E val = e();
        for (auto &p : es[v]){
            if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back());
            if (vis[p.to] > 0) continue;
            E nval = put_edge(dfs(p.to),p.idx);
            outs[v].emplace_back(nval);
            val = merge(val,nval);
        }
        return put_vertex(val,v);
    }
    void bfs(int v){
        int siz = outs[v].size();
        vector<E> lui(siz+1), rui(siz+1);
        lui[0] = e(), rui[siz] = e();
        for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]);
        for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]);
        for (int i = 0; i < siz; i++){
            reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx);
            bfs(es[v][i].to);
        }
        answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v);
    }
};

using reroot_F=pair<ll,ll>;
vector<pair<ll,ll>> p;

reroot_F merge(reroot_F a, reroot_F b){
    return {(a.first+b.first)%mod,(a.second+b.second)%mod};
}
reroot_F e(){
    return {0,0};
}
reroot_F put_edge(reroot_F v, int i){
    return v;
}
reroot_F put_vertex(reroot_F e, int v){
	e.first=(e.first+(1+e.second)*p[v].first)%mod;
	e.second=((1+e.second)*p[v].second)%mod;
	return e;
}
#define reroot_calc reroot_F,reroot_F,merge,e,put_edge,put_vertex

void solve();
// oddloop
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin>>t;
	rep(i,0,t) solve();
}

void solve(){
	int N;
	cin>>N;
	p.resize(N);
	rep(i,0,N){
		ll a;
		cin>>a;
		ll b=1;
		while(b<=a) b*=10ll;
		b%=mod;
		a%=mod;
		p[i]={a,b};
	}
	RerootingDP<reroot_calc> R(N);
	rep(i,0,N-1){
		int a,b;
		cin>>a>>b;
		a--,b--;
		R.add_edge(a,b,i,i);
	}
	R.build();
	auto tmp=R.reroot();
	ll ans=0;
	rep(i,0,N){
		//cout<<tmp[i].first<<" "<<tmp[i].second<<endl;
		ans=(ans+tmp[i].first)%mod;
	}
	cout<<ans<<"\n";
}
0