#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 1 ;
int cnt , h[N] ;
int n ;
struct node {
    int to , nxt , value ;
}e[N << 1] ;
int maxpart , id ;
void add (int a , int b , int c) {
    e[++ cnt].to = b , e[cnt].nxt = h[a] , h[a] = cnt , e[cnt].value = c ;
}
void dfs (int u , int fa , int val) {
    if (val > maxpart) maxpart = val , id = u ;
    for (int i = h[u] ; i ; i = e[i].nxt) {
        int t = e[i].to ;
        if (t == fa) continue ;
        dfs (t , u , val + e[i].value) ;
    }
}

int main () {
    cin >> n ;
    int B = n - 1 ;
    while (B--) {
        int a , b , c ;
        cin >> a >> b >> c ;
        add (a , b , c) ;
        add (b , a , c) ;
    }
    dfs (1 , 0 , 0) ;
    int rot = id , id = maxpart = 0 ;
    dfs (rot , 0 , 0) ; 
    cout << maxpart << endl ;
    return 0 ;
}

动态开点线段树在写法上和普通写法有什么区别吗 $Orz$

请问

for (int i = 1 ; i <= n ; i ++) {
    for (int j = i ; j <= n ; j ++) {

    }
}
这是什么时间复杂度

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,a[105],f[25005],ans,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        f[0]=1;
        k=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            k=max(k,a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=a[i];j<=k;j++)
            {
                f[j]=f[j-a[i]]+f[j];
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(f[a[i]]==1)ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std ;
const int N = 1e4 + 1 ;
int cnt , edgecnt , h[N] ;
int  dfn[N] , low[N] , v[N] , w[N] ;
int scc ;
int tt ;
int top , stk[N] ;
bool in[N] ;
int id[N] ;
int siz[N] ;
int dout[N] , din[N] ;
struct node {
    int to , nxt ;
};
node e[N] ;
int n ;

void add (int a , int b) {
    e[++ cnt].to = b , e[cnt].nxt = h[a] , h[a] = cnt ;
}

void tarls (int u) {
    dfn[u] = low[u] = ++ tt ;
    in[u] = true ;
    stk [++ top] = u ;
    for (int i = h[u] ; i ; i = e[i].nxt) {
        int t = e[i].to ;
        if (!dfn[t]) {tarls (t) , low[u] = min (low[u] , low[t]) ; } 
        else if (in[t]){
            low[u] = min (low[u] , dfn[t]) ;
        }
    }
    if (dfn[u] == low[u]) {
        ++ scc ;
        int y  ;
        do {
            y = stk[top --] ;
            in[y] = false ;
            id[y] = scc ;
            siz[scc] ++ ;

        }while (y != u) ;
    }
}
int main () {
    cin >> n ;
    for (int i = 1 ; i <= n ; i ++) {
        int t ;
        while (cin >> t && t) {
            add (i , t) ;
            v[++edgecnt] = i , w[edgecnt] = t ; 
        }
    }


    for (int i = 1 ; i <= n ; i ++) {
        if (!dfn[i]) tarls (i) ; 
    }

    for (int i = 1 ; i <= edgecnt ; i ++) {
        int x = v[i] , y = w[i] ;
        if (id[v[i]] == id[w[i]]) continue ;
        dout[id[x]] ++ ;
        din[id[y]] ++ ;
    }

    int dinz =0 , doutz = 0 ;

    for (int i = 1 ; i <= scc ; i ++) {
        dinz += (din[i] == 0) ;
        doutz += (dout[i] == 0) ;
    }
     cout << dinz << endl ;
     if (scc == 1) cout << '0' << endl ;
     else cout << max (dinz , doutz) ; 
    return 0 ;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5+1;

LL a[N],n,m,tr[N];

inline int lowbit(int x) {
    return x&(-x);
}

void add(int x,int k) {
    for (int i = x; i <= n ; i+=lowbit(i)) tr[i] += k;
}

LL sum(int x ) {
    LL res = 0;
    for (int i = x ; i ; i-=lowbit(i)) res += tr[i];
    return res;
} 
int main () {

    memset (tr,0,sizeof tr);
    memset (a ,0,sizeof a);


    cin >> n >> m;
    for (int i = 1; i <= n ; i++ ) cin >> a[i];
    for (int i = 1; i <= n ; i++ ) add (i,a[i]-a[i-1]);





    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if (*op == 'C')
        {
            scanf("%d%d", &r, &d);
            add(l, d), add(r + 1, -d);
        }
        else
        {
            printf("%lld\n", sum(l));
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std ;
const int N = 200000 ;
int n ;
int a[N] ;
typedef long long ll ;
ll H1[N] , D1[N] ;
ll tr[N] ;
ll H2[N] , D2[N] ;
int lowbit (int i) {
    return i & (-i) ;
}

void update (int x , int k) {
    for (int i = x ; i <= n ; i += lowbit(i)) tr[i] += k ;
}
long long findans (int x) {
    long long res = 0 ;
    for (int i = x ; i >= 1 ; i -= lowbit(i)) res += tr[i] ;
    return res ;
}

int main () {
    cin >> n ;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i] ;
    for (int i = 1 ; i <= n ; i ++) {
        D1[i] = findans (a[i] - 1) ;   
        H1[i] = findans (n) - findans (a[i] - 1) ;  
        update (a[i] , 1) ;    
    }
    long long  res1  = 0 , res2 = 0 ;
    for (int i = 1 ; i <= n ; i ++) tr[i] = 0 ; 
    for (int i = n ; i ; i --) {
        H2[i] = findans (n) - findans (a[i] - 1) ;
        D2[i] = findans (a[i] - 1) ; 
        update (a[i] , 1) ;
    }
    for (int i = 1 ; i <= n ; i ++) {
        res1 += D1[i] * D2[i] ;
        res2 += H1[i] * H2[i] ;
    }
    cout << res2 << " " << res1 ;

    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std ;
const int M = 3e5 + 1 , N = 17 ;
long long f[M] , a[N] ;
int n , m ;

int main () {
    cin >> n >> m ;
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
    f[0] = 1 ;

    for (int i = 1 ; i <= n ; i ++ ) {
        for (int j = a[i] ; j <= m ; j ++) {
            f[j] += f[j - a[i]] ;
        }
    } 
    cout << f[m] << endl ;

    return 0 ;
}

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int v[4] = {10, 20, 50, 100};
int f[N];

int main() {
    cin >> n;

    f[0] = 1;
    for (int i = 0; i < 4; i ++ )
        for (int j = v[i]; j <= n; j += 10 )
            f[j] += f[j - v[i]] ;

    cout << f[n] << endl ;

    return 0;
}

#include <bits/stdc++.h>
using namespace std ;
const int N = 1e2 + 1 , M = 1e4 + 1 ;

int n , m ;
int a[N] , f[M] ;

int main () {
    cin >> n >> m ;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a[i] ;
    }
    f[0] = 1 ;
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = m ; j >= a[i] ; j --) {
            f[j] += f[j - a[i]] ;
        }
    }

    cout << f[m] << endl ;
    return 0 ;
}